GEN 3837
Computational Complexity
Stanford University · UGRD · Fall 2026
1 section
Catalog description
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.
Sections
Current meeting, instructor, credit, and enrollment details
001
Availability not recently verifiedClass #stanford-3837Fall 2026UGRD3 credits
- Days & times
- No scheduled meeting time
- Meeting dates
- —
- Location
- —
- Instructor
- Staff
Class numbers and section codes come from the registrar.
Spot missing or incorrect course data?