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, 2:30 - 3:45 p.m., AKW 307
Instructor: Joan Feigenbaum
Office: AKW 512
Telephone: 203-432-6432
Office hours: Thursdays 11:30am - 12:30pm and by appointment
TA: David.Costanzo@yale.edu, AKW 301, Thursdays 4:00pm - 5:00pm
Assistant: Judi.Paige@yale.edu, 203-436-1267, AKW 507A

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.

Textbook: Complexity Theory: A Modern Approach, by Sanjeev Arora and Boaz Barak

Grading

Tentative Course Schedule

Lectures

  1. September 3, 2009: Course outline, introduction [Slides]
  2. September 8, 2009: Turing-machine model, formal definitions of polynomial time and nondeterministic polynomial time, many-to-one polynomial-time reductions, definition of NP completeness. Thanks to Raonne Barbosa Vargas, who took CPSC 568 last year, we have this demo of a Turing Machine recognizing a palindrome.
  3. September 10, 2009: Reducing SAT to 3SAT, start on proof of Cook's Theorem
  4. September 15, 2009: Finish proof of Cook's Theorem, introduction to diagonalization and proof of the existence of an undecidable set, statement of DTIME, NTIME, and DSPACE hierarchy theorems, diagonalization proof that DTIME(n^2) is properly contained in DTIME(n^3), definition of an oracle TM
  5. September 17, 2009: The Baker-Gill-Solovay Theorem
  6. September 22, 2009: Revisiting time constructibility, examples of functions that are not time-constructible; further discussion of relativized computation and why the existence of an oracle relative to which P ≠ NP does not imply that P ≠ NP; introduction to space-bounded computation and configuration graphs
  7. September 24, 2009: Savitch's Theorem; PSPACE-completeness of TQBF
  8. September 29, 2009: Logspace reductions; NL-completeness of PATH; The Immerman-Szelepcsenyi Theorem
  9. October 1, 2009: Making Cook's reduction parsimonious; Introduction to the PH
  10. October 6, 2009: Circuits and Turing Machines that take advice; logspace-uniform circuits recognize exactly P; P/poly contains undecidable languages; Karp-Lipton Theorem
  11. October 8, 2009: Probabilistic Turing Machines; the complexity classes RP, coRP, ZPP, and BPP; the use of Chernoff bounds to decrease the probability of error; Adleman's Theorem (BPP is contained in P/poly)
  12. October 13, 2009: Review for Exam 1
  13. October 15, 2009: Exam1
  14. October 20, 2009: The Sipser-Gacs Theorem; Introduction to IP; Pairwise-independent hash-function families
  15. October 22, 2009: Proof that the set of all affine functions over a finite field is a pairwise-independent hash-function family; the Goldwasser-Sipser lower-bound protocol
  16. October 27, 2009: IP is contained in PSPACE, Arithmetization of 3CNF formulae
  17. October 29, 2009: Interactive proof system for co-3SAT
  18. November 3, 2009: Interactive proof system for TQBF
  19. November 5, 2009: More on the interactive proof system for TQBF. Introduction to multiprover interactive proof systems.
  20. November 10, 2009: Using MIP = NEXP to prove a hardness-of-approximation result for the clique-number problem. Introduction to #P.
  21. November 12, 2009: Proof of the USAT version of the Valiant-Vazirani lemma; definition of parity-P; amplification of correctness probability in the parity-P version of the Valiant-Vazirani lemma.
  22. November 17, 2009: Generalizing Valiant-Vazirani: For any L in the PH, there is a ppt reduction A such that membership of x in L is, with probability exponentially close to 1, equivalent to membership of A(x) in parity-P.
  23. November 19, 2009: Derandomization to complete the proof of Toda's Theorem: PH is contained in P^{#SAT}
  24. December 1, 2009: Review for Exam 2
  25. December 3, 2009: Exam 2

Homework

Hand in problem sets via the TA's mailbox on the first floor, or just hand them directly to him. He's generally either in his office (AKW 301) or the open zoo from late morning til evening on weekdays. You may also LaTex the problem set nicely and email the pdf to the TA.

  1. HW1(due Mon, Sept 21): 1.2, 1.5, 1.15, 2.5, 2.10, 2.13, 2.30
  2. HW2(due Thurs, Oct 1): 3.2, 3.3, 3.6, 4.4, 4.6, 4.8, 4.10
  3. HW3(due Tues, Oct 13): 5.7, 5.9, 5.11, 6.3, 6.4, 6.9
  4. HW4(due Mon, Nov 2):7.6, 7.7, 7.10, 8.1, 8.9, 8.10
  5. HW5(due Tues, Nov 17): 8.7, 8.8, 17.1. 17.2, 17.3, 17.4
  6. HW6(due Tues, Dec 1): 6.14, 6.15, 7.9, 8.2, 8.5, 7.11 (optional)

Reading Assignments:

  1. Skim Introduction and Chapter 0
  2. Read sections 1.1, 1.2, 1.3, and 1.6
  3. Read discussion of Ladner's Theorem in Chapter 3
  4. Sections 7.6 and 7.7 of Arora-Barak
  5. For HW5, read Sections 17.1, 17.2, and 17.3 of Arora-Barak.