printer friendly pageCS 254: Computational Complexity
An introduction to computational complexity theory. Topics include the P versus NP problem; diagonalization; space complexity: PSPACE, Savitch's theorem, and NL=coNL; counting problems and #P-completeness; circuit complexity; pseudorandomness and derandomization; complexity of approximation; quantum computing; complexity barriers. Prerequisites: 154 or equivalent; mathematical maturity.
Terms: Win
| Units: 3
Instructors:
Tan, L. (PI)
;
Zhong, J. (TA)
Filter Results: