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 (2025-04-22):
P and NP intuitively
- Video 2-2 (2025-04-22):
Models of computation: word-RAM
- Video 2-3 (2025-04-23):
Models of computation: Turing Machines
- Video 2-4 (2025-04-23):
P and NP formally
- Video 2-5 (2025-04-23):
Nondeterminism = Verification
- Video 2-6 (2025-04-23):
Karp-Reductions and NP completeness
- Video 2-7 (2025-04-23):
Example NP-completeness prooof (overview)
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