Complexity Theory
A 18-module path through complexity theory, in study order from foundations to the frontier.
Modules
- Measuring Time Complexity
- The Class P
- Verifiers and Certificates
- The Class NP
- Polynomial-Time Mapping Reductions
- NP-Completeness
- SAT and 3-SAT
- The Cook-Levin Theorem
- Classic NP-Complete Problems: Clique and Vertex Cover
- Hamiltonian Path and Circuit Problems
- coNP
- Measuring Space Complexity
- PSPACE
- Savitch's Theorem
- PSPACE-Completeness
- L and NL
- The Time and Space Hierarchy Theorems
- Randomized and Higher Complexity: BPP, the Polynomial Hierarchy, and Interactive Proofs