Site Map | College of Engineering | UC Davis | MyUCDavis

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%)

Catalog Description:
Time and space complexity classes. Reductions, completeness, and the role of randomness. Logic and undecidability.

Goals:
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:

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

Textbook:
C. Papadimitriou, Computational Complexity, Addison Wesley, 1994

Instructor: P. Rogaway

Prepared by: P. Rogaway (January 2002)

Overlap Statement:
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.

1/02

Back to Course Descriptions