Computational Complexity in Theory and in Practice
summary
Survey of concrete claims and tools: Cook's reduction makes SAT the P vs NP focal point; NP-completeness follows by polynomial-time reductions. Industrial SAT succeeds via resolution-based SAT solvers despite worst-case exponential complexity. Linear and integer programming get both theoretical advances (Karmarkar, Lee and Sidford interior‑point methods) and practical wins (LP + cutting planes yields exact TSP solutions up to 80,000-city exact TSP via LP+cuts); approximation results include Christofides 3/2 for symmetric TSP and recent constant‑factor but impractical asymmetric algorithms.
AI-written summary · about
chapters (10)
- 0:00Start
- 2:46Polynomial-Time Sequential, Deterministic Algorithms
- 13:59SATISFIABILITY (an example)
- 16:45NP-completeness via Reducibility
- 21:38Twenty-One NP-Complete Problems
- 25:35Complexity of 3-SAT
- 46:32Traveling-Salesman Problem
- 54:48Linear Programming Relaxation of TSP
- 56:55Solving the TSP
- 59:16Asymmetric TSP
related talks
01h 07mComputational Complexity of Polynomial Time Problems: Introduction
58mCircuit Complexity and Connections I
33mUnification of SAT, Constraint Programming, and Pseudo-Boolean Solving: A Personal Story
01h 07mSatisfiability Algorithms I
01h 01mCircuit Complexity and Connections II
01h 03mRecent Advances in FPT and Exact Algorithms for NP-Complete Problems
17mSatisfiability Algorithms Based on Concentrated Shrinkage
29mImproved Deterministic Algorithms for Sparse Max-SAT