Computational Complexity
Lecture
Main Campus
Course 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.
CS 254
Units: 3
See When It's Offered opens a new window opens in a new tab
Typically Offered
Not Available
Grading Basis
Letter or Credit/No Credit
Class Level
Graduate
Instructional Mode
In Person
Gen Ed Requirement(s)
None