CSE200 - Computability and Complexity

Units: 

 4

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: 

Study equivalent to material presented in CSE 105.

Revised Fall 2002