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