CS 254B
Computational Complexity II
A continuation of CS254 (Computational Complexity). Topics include Barriers to P versus NP; The relationship between time and space, and time-space tradeoffs for SAT; The hardness versus randomness paradigm; Average-case complexity; Fine-grained complexity; Current and new areas of complexity theory research. Prerequisite: CS254.
Topics
- Barriers to P versus NP
- The relationship between time and space
- and time-space tradeoffs for SAT
- The hardness versus randomness paradigm
- Average-case complexity
- Fine-grained complexity
- Current and new areas of complexity theory research
Topics explicitly listed in official catalogue description
Sources
- Course catalogue ↗2026-2027