CSE531: Computational Complexity I

Catalog Description: Deterministic and nondeterministic time and space complexity, complexity classes, and complete problems. Time and space hierarchies. Alternation and the polynomial-time hierarchy. Circuit complexity. Probabilistic computation. Exponential complexity lower bounds. Interactive proofs. Prerequisite: either CSE 311 or equivalent.

Prerequisites: CSE 311 or equivalent.
Credits: 4.0

---

Portions of the CSE531 web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE531 Web: © 1993-2024, Department of Computer Science and Engineering, University of Washington. Administrative information on CSE531 (authentication required).