CSE531: Computational Complexity I
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.Prerequisites: CSE majors only; CSE 322 or equivalent.
Credits: 4
Portions of the CSE 531 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 531 Web: © 1993-2012, Department of Computer Science and Engineering, University of Washington. Administrative information on CSE531 (authentication required).
- Current Quarter
- Prerequisites
- Previous Quarters
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX