CSE200 - Computability and Complexity
Computability review, including halting problem, decidable sets, r.e. sets, many-one reductions; TIME(t(n)), SPACE(s(n)) and general relations between these classes; L, P, PSPACE, NP; NP - completeness; hierarchy theorems; RP, BPP.
Textbooks:
- Completeness: A Guide to Intractability, Garey and Johnson
- Computational Complexity, Arora and Barak
Prerequisites:
CSE 105 or equivalent
Revised Fall 2002
