CPSC468/568: Computational Complexity

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.

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

• Homeworks: 10% each (x6 = 60% total)
• Exams:          20% each (x2 = 40% total)

Tentative Course Schedule

• HW1 due Tues, Sep 21
• HW2 due Thur, Sep 30
• HW3 due Tues, Oct 12
• Ex1 in class on Thur, Oct 14
• Drop Date for Fall semester: Fri, Oct 22
• HW4 due Thur, Nov 04
• HW5 due Tues, Nov 16
• HW6 due Tues, Nov 30
• Ex2 in class on Thur, Dec 02

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

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