CPSC468/568: Computational Complexity

Course information

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.

Course Schedule

• September 25, 2008: First HW due
• October 14, 2008: Second HW due
• October 16, 2008: First Exam (in class)
• October 24, 2008: Fall semester drop date
• October 30, 2008: Third HW due
• November 13, 2008: Fourth HW due
• December 2, 2008: Fifth HW due
• December 4, 2008: Second Exam (in class)

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
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

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)