Complexity Theory
Computer Science 181D
Harvey Mudd College
Syllabus, Fall 2012

Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1258
Phone: x18976
E-mail: hadas@cs.hmc.edu
Office Hours: Please see my schedule
Course Time and Location: T, Th, 9:35-10:50 AM, Beckman B115
Course Grutors: Dave Lingenbrink, John Peebles, Xanda Schofield
Course Homepage: www.cs.hmc.edu/courses/2012/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 important before embarking on complexity theory. Moreover, at the end of the course, we'll use the techniques and ideas that we've learned in both computability and complexity theory to prove the famous Godel Incompleteness Theorem!

Here are some of the topics that we will explore in this course:

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

Attendance and Worksheets

Attendance is important because much of the material will be presented differently than in standard textbooks and you will learn a lot from the questions, comments, and insights of your classmates. Therefore, please attend every lecture and make every effort to arrive on time in order to avoid distracting the class. If you need to miss a class or arrive late, please let me know in advance.

There will be an in-class worksheet in each of the 14 class periods. Worksheets are submitted at the end of class and will be scored "check" (made good effort; full credit) or "no check" (absent or insufficient effort; no credit). Each worksheet is worth 1% of the course grade.

You may collect your worksheet in the bin outside the CS main office. They will be returned there within six hours of the end of lecture (5 PM that day).

If you are sick or have some other extenuating circumstances that prohibit you from coming to class, write to me before class so that you can get credit for your worksheet.

Assignments

Exam

Grades

• Homework Assignments: 66% (6 homework assignments, 11% each)
• Take-home Exam: 20%
• Attendance and Worksheets: 14% (1% per worksheet)

Euros

Collaboration Policy

Collaboration on homeworks is encouraged. This means that you may discuss approaches to solving a problem with anyone in the class. However, you should not share or look at any written solutions to problems.

Submitting Homework

On each submitted homework, please indicate the names of all people with whom you discussed your solutions.

You may typeset or hand-write homeworks, but your submissions must be in pdf form and will be submitted on the CS submission system at: http://www.cs.hmc.edu/~submissions/submissionsFall12. This system automatically records your Euro usage and allows you to view your grades. Please change your password after your first login.