## 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.

Terms: Win
| Units: 3

Instructors:
Tan, L. (PI)
;
Lecomte, V. (TA)

## 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.

Terms: Spr
| Units: 3

Instructors:
Tan, L. (PI)
;
Lecomte, V. (TA)

Filter Results: