Complexity Theory

Catalog Description: Deterministic, nondeterministic, alternating, and probabilistic Turing machines. Time and space complexity, complexity classes, complexity hierarchies, and provably intractable problems.
Prerequisites: CSE majors only; Recommended: CSE 531.
Credits: 4

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