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
- Video 2-1 (2026-10-15, 17:02):
P and NP Informally
- Video 2-2 (2026-10-15, 9:36):
Models of Computation
- Video 2-4 (2026-10-15, 12:59):
The Classes P and NP
- Video 2-5 (2026-10-15, 10:37):
Nondeterminism = Verification
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