ECS 220 THEORY OF COMPUTATION (4) III
Lecture: 3 hours
Discussion: 1 hour
Prerequisite: Courses ECS 120, ECS 122A
Grading: Letter; homework (40%), one midterm (20%), final (40%)
Time and space complexity classes. Reductions, completeness, and the role of randomness. Logic and undecidability.
To provide students with a grounding in the theory of computation, and to help them develop the skills necessary to do and understanding more complex proofs in theoretical computer science.
Expanded Course Description:
- Turing machines and Turing-equivalent models of computation. Turing-undecidable problems from a variety of domains.
- First order logic, completeness, second-order logic, undecidability and incompleteness, the recursion theorem.
- Complexity classes, the time and space hierarchy, Savitch’s theorem, reductions, completeness. The polynomial time hierarchy. Decision vs. search. NL = coNL.
- The Cook-Levin theorem. NP-Complete problems. PSPACE completeness. Practice with reductions.
- Randomized computations, BPP, problems for which randomness provably helps. Interactive proofs. IP=PSPACE. PCP (Probabilistically Checkable Proofs).
- Approximation algorithms. Non-approximability results.
Possible Textbooks (check the current course listing before purchasing):
C. Moore, S. Mertens, The Nature of Computation, Oxford, 2011
C. Papadimitriou, Computational Complexity, Addison Wesley, 1994
Instructors: P. Rogaway, D. Doty
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.