ECS 220: Theory of Computation

Subject
ECS 220
Title
Theory of Computation
Status
Active
Units
4.0
Effective Term
2020 Winter Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
Description
Time and space complexity classes. Reductions, completeness, and the role of randomness. Logic and undecidability.
Prerequisites
ECS 120; ECS 122A
Enrollment Restrictions
Open to Graduate Students in Computer Science only.

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.

Course Category