main page — CS 627 Advanced Algorithms
Unit 2: Complexity Theory Recap
This unit covers
- Turing machines, word-RAM model
- nondeterminism
- time and space complexity
- complexity classes P and NP
- polynomial-time reductions
- NP-completeness
Material
- slides
- Turing Machine Simulator
- 3-SAT to Vertex Cover
- Video 2-1 · transcript (2026-10-15, 17:02):
P and NP Informally
- Video 2-2 · transcript (2026-10-15, 9:36):
Models of Computation
- Video 2-3 · transcript (2026-10-15, 26:32):
Turing Machines
- Video 2-4 · transcript (2026-10-15, 12:59):
The Classes P and NP
- Video 2-5 · transcript (2026-10-15, 10:37):
Nondeterminism = Verification
- Video 2-6 · transcript (2026-10-19, 21:27):
VP = NP
- Video 2-7 · transcript (2026-10-19, 24:58):
Karp-Reductions and NP-Completeness
- Video 2-8 · transcript (2026-10-19, 28:34):
Example of an NP-Hardness Reduction
- Video 2-9 · transcript (2026-10-22, 21:44):
Important NP-Complete Problems
- Video 2-10 · transcript (2026-10-22, 23:22):
Complexity for Optimization Problems
Further reading and sources
A detailed and well-written introduction to complexity theory is given in the following book. (They study $k$-tape Turing machines as the default and don’t define computations via configurations.)
- S. Arora and B. Barak: Computational Complexity: A Modern Approach
Much closer to our formalization of Turing machines and including a detailed proof of the Cook-Levin theorem is our German book