CSE532: 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 major and CSE 531.
Credits: 3.0

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