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: David Costanzo
Office: AKW 301 (or open zoo)
E-mail: firstname.lastname@yale.edu
Office hours: Tuesdays, 4:00pm - 5:00pm

Textbooks:

Grading


Tentative Course Schedule


Lectures

  1. September 2, 2010: Course outline, introduction [Slides]
  2. September 7, 2010: Turing-machine model, Palindrome example, nondeterminism, running Time, time-constructibility.
    Thanks to Raonne Barbosa Vargas, who took this course in 2008, we have this demo of a Turing Machine recognizing a palindrome.
  3. September 9, 2010: Definitions of P, NP, many-to-one polynomial-time reduction, and NP-completeness. Cook's Theorem.
  4. September 14, 2010: Introduction to simulation and diagonalization, undecidability of the Halting Problem, DTIME, NTIME, and DSPACE hierarchy theorems, existence of a function that is not time-constructible
  5. September 16, 2010: Oracle Turing Machines, the Baker-Gill-Solovay Theorem.
  6. September 21, 2010: Space-bounded computation, configuration graphs, PATH is in NL, Savitch's Theorem.
  7. September 23, 2010: Logspace reductions, PATH is NL-complete, the Immerman-Szelepcsenyi Theorem.
  8. September 28, 2010: TQBF is PSPACE-complete, making Cook's reduction parsimonious
  9. September 30, 2010: The Polynomial Hierarchy (PH), Alternating Turing Machines
  10. October 5, 2010: Polynomial-sized circuits, P is contained in P/poly, and the Karp-Lipton Theorem
  11. October 7, 2010: Equivalence of three definitions of the PH: Quantified boolean formulas with a constant number of quantifier alternations; Alternating TMs with a constant number of quantifier alternations; Oracle TMs with access to an oracle for the Sigma level one below. Introduction to polynomial-time probabilistic computation.
  12. October 12, 2010: Review for Exam 1
  13. October 14, 2010: [Exam 1] [Solutions]
  14. October 19, 2010: Definitions of RP, coRP, and BPP, proof that PRIMES is in coRP, Adleman's Theorem (BPP is contained in P/poly), and the Sipser-Gacs Theorem (BPP is contained in the second level of the PH).
  15. October 21, 2010: Introduction to IP, Graph Nonisomorphism is in IP, Pairwise-independent hash-function families.
  16. October 26, 2010: Arthur-Merlin games and the Goldwasser-Sipser lower-bound proof system. Probabilistic polynomial-time reductions, probabilistic space-bounded computation.
  17. October 28, 2010: Arithmetization of boolean formulas, coNP is contained in IP.
  18. November 2, 2010: IP is contained in PSPACE, multi-prover interactive proof systems, "oracle proof systems," and checkers.
  19. November 4, 2010: IP=PSPACE, using MIP = NEXP to prove a hardness-of-approximation result for the clique-number problem.
  20. November 9, 2010: If GI is NP-complete, then the PH collapses at the second level. The USAT version of the Valiant-Vazirani lemma.
  21. November 11, 2010: Definitions of #P and parity-P, the parity-P version of the Valiant-Vazirani lemma.
  22. November 16, 2010: The PH is in BPP^{parity-P}.
  23. November 18, 2010: Completing the proof that the PH is contained in P^{#P} (Toda's Theorem) by "determinizing" the result presented in Lecture 22.
  24. November 30, 2010: Review for Exam 2
  25. December 2, 2010: [Exam 2] [Solutions]


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. Alternatively, you may LaTex the problem set nicely and email the pdf.

  1. HW1 (due Tues, Sep 21): 1.2, 1.5, 1.15, 2.5, 2.13, 2.29, 2.30
  2. HW2 (due Thur, Sep 30): 3.3, 3.4, 4.4, 4.6, 4.8, 4.10, 3.6(EC)
  3. HW3 (due Tues, Oct 12): 5.7, 5.9, 5.10, 6.3, 6.4, 6.9
  4. HW4 (due Thur, Nov 4): 7.6, 7.7, 7.10, 8.9, 8.10, 8.11
  5. HW5 (due Tues, Nov 16): 7.9, 8.2, 8.5, 8.7, 8.8, 17.4, 7.11*
  6. HW6 (due Tues, Nov 30): 7.8, 8.1, 8.3, 8.12, 17.1

Reading Assignments:

  1. September 2, 2010: Skim Introduction and Chapter 0
  2. September 7, 2010: Read sections 1.1, 1.2, 1.3, and 1.6
  3. September 14, 2010: Read sections 1.5 and 1.7
  4. September 30, 2010: Read section 5.4
  5. October 7, 2010: Read sections 6.1.2 and 6.3
  6. November 9, 2010: Read sections 17.1, 17.2, and 17.3