CS 254
Computational Complexity
An introduction to computational complexity theory. Topics include the P versus NP problem and other major challenges of complexity theory; Space complexity: Savitch's theorem and the Immerman-Szelepscényi theorem; P, NP, coNP, and the polynomial hierarchy; The power of randomness in computation; Non-uniform computation and circuit complexity; Interactive proofs. Prerequisites: 154 or equivalent; mathematical maturity.
Topics
- the P versus NP problem and other major challenges of complexity theory
- Space complexity: Savitch's theorem and the Immerman-Szelepscényi theorem
- coNP
- and the polynomial hierarchy
- The power of randomness in computation
- Non-uniform computation and circuit complexity
- Interactive proofs
Topics explicitly listed in official catalogue description
Sources
- Course catalogue ↗2026-2027