CPSC468/568: Computational Complexity

Course Information | Course Schedule | Lectures | Homework

Course information

Description: Introduction to the theory of computational complexity. Basic complexity classes, including polynomial time, nondeterministic polynomial time, probabilistic polynomial time, polynomial space, logarithmic space, and nondeterministic logarithmic space. The roles of reductions, completeness, randomness, and interaction in the formal study of computation.

Location: T/Th, 1:00 - 2:15 p.m., AKW 500

Instructor: Joan Feigenbaum
Office: AKW 512 (51 Prospect Street, New Haven)
Telephone: 203-432-6432
Office hours: Thursdays 11:30am - 12:30pm, and by appointment
Assistant:
Judi.Paige@yale.edu
AKW 507A
8:30am - 4:30pm
203-436-1267

Note: Professor Feigenbaum suffers from Repetitive Strain Injury and cannot handle large amounts of email. Do NOT send her email about CPSC468/568; instead, please contact her by phone, through the TA, or through her assistant Judi Paige.


TA: Nicholas Ruozzi
Office: AKW 202
E-mail: firstname.lastname@yale.edu
Office hours: Monday 1pm-2pm

Textbooks:


Course Schedule


Lectures

  1. September 4, 2008: Course outline, introduction [Slides]
  2. September 9, 2008: Turing-machine model, formal definitions of polynomial time and nondeterministic polynomial time, many-to-one polynomial-time reductions, definition of NP completeness
  3. September 11, 2008: Reducing SAT to 3SAT, example of a set known to  be in NP and in coNP but not known to be in P, start on proof of  Cook's Theorem
  4. September 16, 2008: Finish proof of Cook's Theorem, introduction to  diagonalization and proof of the existence of an undecidable set
  5. September 18, 2008: Statement of DTIME, NTIME, and DSPACE hierarchy  theorems, diagonalization proof that DTIME(n) is properly contained in DTIME(n^2), definition of an oracle TM, statement of  Baker-Gill-Solovay theorem
  6. September 23, 2008: Proof of the Baker-Gill-Solovay theorem, review of "what we have learned" so far about time complexity
  7. September 25, 2008: Space-bounded computation, Savitch's theorem, definitions of the classes L and NL and the PATH problem
  8. September 30, 2008: TQBF is PSPACE-complete, PH, relating PH to NP and PSPACE
  9. October 2, 2008: PATH in is NL, logspace reductions, the Immerman-Szelepcsenyi theorem
  10. October 7, 2008: Circuits, P/poly, the Karp-Lipton theorem
  11. October 9, 2008: Alternating TMs and the polynomial hierarchy using oracle machines
  12. October 14, 2008: Review for Exam 1
  13. October 16, 2008: [Exam 1] [Solutions]
  14. October 21, 2008: Probabilistic Turing Machines; RP, co-RP, and BPP; using the Chernoff Bound on the tails of the binomial distribution to obtain exponentially small error probability
  15. October 23, 2008: Adleman's Theorem (BPP is contained in P/poly) and the Sipser-Gacs Theorem (BPP is contained in the PH)
  16. October 28, 2008: Interactive Proof Systems; GNI is contained in IP
  17. October 30, 2008: Pairwise Independent Universal Hash Functions and the Sipser-Goldwasser Lower Bound Proof System
  18. November 4, 2008: Program checkers and multiprover interactive proof systems,arithmetization of boolean formulas
  19. November 6, 2008: Proof that co-3SAT is in IP
  20. November 11, 2008: MIP = NEXP implies that the clique number of a graph cannot beapproximated within a factor of 2 unless EXP = NEXP.
  21. November 13, 2008: The Valiant-Vazirani Lemma
  22. November 18, 2008: Toda's Theorem, part I
  23. November 20, 2008: Toda's Theorem, part II
  24. December 2, 2008: Review for Exam 2
  25. December 4, 2008: [Exam 2] [Solutions]


Homework

  1. HW1(due Sept. 25): 1.1, 1.5, 1.15, 2.5, 2.7, 2.15, 2.25, 2.30
  2. HW2(due Oct. 14): 3.2, 3.4, 4.3, 4.4, 4.6, 4.10
  3. HW3(due Oct. 30): 5.9, 6.14, 7.6, 7.10, 8.1, 8.9
  4. HW4(due Nov. 13): 8.2, 8.6, 8.8, 8.10 and 8.11
  5. HW5(due Dec. 2): 17.1, 17.2, 17.3, 17.4, and 17.5

Reading Assignments:

  1. Skim Introduction and Chapter 0, Example 1.1, Section 1.3.1, and Section 1.6
  2. Read the proof of theorem 1.9 and sections 1.5.1, 1.52 (just for fun), and 3.3
  3. Read carefully Section 3.1 (special case of DTIME hierarchy theorem)
  4. Read carefully the proof of Theorem 4.18 (PATH is NL-complete)