CSE531: Computational Complexity I

Catalog Description: Computational models including deterministic and nondeterministic Turing machines, and techniques for analyzing them. Fundamentals of computability theory and undecidability. Fundamentals of computational complexity theory and NP-completeness. .

Prerequisites: CSE majors only; CSE 322 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 creditied. The CSE531 Web: © 1993-2021, Department of Computer Science and Engineering, Univerity of Washington. Administrative information on CSE531 (authentication required).