Print Settings

CS 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.
Last offered: Autumn 2016 | Units: 3
© Stanford University | Terms of Use | Copyright Complaints