Computational Complexity
Download as PDF
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.
Grading Basis
ROP - Letter or Credit/No Credit
Min
3
Max
3
Course Repeatable for Degree Credit?
No
Course Component
Lecture
Enrollment Optional?
No
Does this course satisfy the University Language Requirement?
No
Programs
CS254
is a
completion requirement
for:
- (from the following course set: )
- (from the following course set: )
- (from the following course set: )