Computer Science 182
Computational Complexity Theory (a.k.a. "Theocomp")
Syllabus, Fall 2010
Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1245
Phone: x18976
E-mail: hadas@cs.hmc.edu
Office Hours: Please see my schedule
Course Time and Location: Mondays and Wednesdays, 2:45-4 PM,
Jacobs B132
Course Grader: Josh Ehrlich
Course Homepage:
www.cs.hmc.edu/courses/2010/fall/cs182
What Is This Course About?
This course is primarily about computational complexity theory, the
study of the "hardness" of computational problems. However, we begin
with a brief section on computability theory (some review from CS 81
but mostly new material), since a firm grounding in this area is
necessary to understand some of the issues in complexity theory.
Here is a tentative list of topics:
Computability Theory
- Turing Machines and decision, function, and enumeration
problems
- Diagonalization, the halting problem, reductions, and Rice's
Theorem
- The Recursion Theorem and its implications
Computational Complexity Theory
- Time and space measures on Turing Machines and other models of computation
- Polynomial-time and log-space reductions, P, NP, and NP-completeness
- Cook's Theorem
- Strong NP-completeness
- NP and co-NP
- The complexity of approximation
- The polynomial hierarchy and PSPACE-completeness
- Savitch's Theorem
- Logspace and NL-completeness
- The speedup, hierarchy, and gap theorems
Texts
There is no textbook for the course. Lectures will be self-contained.
Sipser's book (also used in CS 81) is a good resource and many of the
topics that we will cover in this course are covered in the last few
chapters of that book.
Attendance and Participation
Please attend every lecture and make every effort to arrive on time.
If you need to miss a class or arrive late, please let me know in advance.
Assignments
There will typically be one assignment each week, given on Wednesday and
due the following Wednesday.
Exams
There will be one exam in this course, an open-notes
take-home exam near the end of the course.
Grades
The components of the course are worth the following:
Homework Assignments: 80%
Take-home Exam: 20%
Collaboration Policy
Collaboration on homeworks is encouraged. This means that you may
discuss approaches to solving a problem with anyone in the class.
On each submitted homework, please indicate the names of all people
with whom you discussed your solutions. Unless indicated otherwise,
no written sources (other than your own notes) should be consulted in
solving homework problems.
There should be no collaboration on the take-home exam.
All parties, including off-campus students,
are expected to follow the Harvey Mudd Honor code.