ECS 220: Theory of Computation

Summary of Course Content
I. Turing machines and Turing-equivalent models of computation. Turing-undecidable problems from a variety of domains. II. First order logic, completeness, second-order logic, undecidability and incompleteness, the recursion theorem. III. Complexity classes, the time and space hierarchy, Savitch's theorem, reductions, completeness. The polynomial time hierarchy. Decision vs. search. NL = coNL. IV. The Cook-Levin theorem. NP-Complete problems. PSPACE completeness. Practice with reductions. V. Randomized computations, BPP, problems for which randomness provably helps. Interactive proofs. IP=PSPACE. PCP (Probabilistically Checkable Proofs). VI. Approximation algorithms. Non-approximability results.

Illustrative Reading
C. Papadimitriou, Computational Complexity, Addison Wesley, 1994

Potential Course Overlap
This course does not have a significant overlap with any other course. NP-completeness is discussed, at a lower and more pragmatic level, in ECS 120.