main page — CS 627 Advanced Algorithms
Unit 2: Complexity Theory Recap
This is an archived version of this module from Summer 2025.
Click here for the current iteration.
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, 12:04):
P and NP intuitively
- Video 2-2 (2025-04-22, 14:46):
Models of computation: word-RAM
- Video 2-3 (2025-04-23, 35:40):
Models of computation: Turing Machines
- Video 2-4 (2025-04-23, 11:57):
P and NP formally
- Video 2-5 (2025-04-23, 17:06):
Nondeterminism = Verification
- Video 2-6 (2025-04-23, 8:01):
Karp-Reductions and NP completeness
- Video 2-7 (2025-04-23, 4:54):
Example NP-completeness prooof (overview)
- Video 2-8 (2025-05-13, 12:12):
Further hard problems
- Video 2-9 (2025-04-13, 31:28):
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