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: 
2034326432 
Office hours: 
Thursdays 11:30am  12:30pm, and by appointment 
Assistant: 
Judi.Paige@yale.edu 
AKW 507A 
8:30am  4:30pm 
2034361267 


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 
Email: 
firstname.lastname@yale.edu 
Office hours: 
Monday 1pm2pm 

Textbooks:
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
 September 4, 2008: Course outline, introduction
[Slides]
 September 9, 2008: Turingmachine model, formal definitions of polynomial time and nondeterministic polynomial time, manytoone polynomialtime reductions, definition of NP completeness
 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
 September 16, 2008: Finish proof of Cook's Theorem, introduction to diagonalization
and proof of the existence of an undecidable set
 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 BakerGillSolovay theorem
 September 23, 2008: Proof of the BakerGillSolovay theorem, review of "what we have learned" so far about time complexity
 September 25, 2008: Spacebounded computation, Savitch's theorem, definitions of the classes L and NL and the PATH problem
 September 30, 2008: TQBF is PSPACEcomplete, PH, relating PH to NP and PSPACE
 October 2, 2008: PATH in is NL, logspace reductions, the ImmermanSzelepcsenyi theorem
 October 7, 2008: Circuits, P/poly, the KarpLipton theorem
 October 9, 2008: Alternating TMs and the polynomial hierarchy using oracle machines
 October 14, 2008: Review for Exam 1
 October 16, 2008: [Exam 1] [Solutions]
 October 21, 2008: Probabilistic Turing Machines; RP, coRP, and
BPP; using the Chernoff Bound on the tails of the binomial
distribution to obtain exponentially small error probability
 October 23, 2008: Adleman's Theorem (BPP is contained in P/poly)
and the SipserGacs Theorem (BPP is contained in the PH)
 October 28, 2008: Interactive Proof Systems; GNI is contained in IP
 October 30, 2008: Pairwise Independent Universal Hash Functions
and the SipserGoldwasser Lower Bound Proof System
 November 4, 2008: Program checkers and multiprover interactive proof systems,arithmetization of boolean formulas
 November 6, 2008: Proof that co3SAT is in IP
 November 11, 2008: MIP = NEXP implies that the clique number of a graph cannot beapproximated within a factor of 2 unless EXP = NEXP.
 November 13, 2008: The ValiantVazirani Lemma
 November 18, 2008: Toda's Theorem, part I
 November 20, 2008: Toda's Theorem, part II
 December 2, 2008: Review for Exam 2
 December 4, 2008: [Exam 2] [Solutions]
Homework
 HW1(due Sept. 25): 1.1, 1.5, 1.15, 2.5, 2.7, 2.15, 2.25, 2.30
 HW2(due Oct. 14): 3.2, 3.4, 4.3, 4.4, 4.6, 4.10
 HW3(due Oct. 30): 5.9, 6.14, 7.6, 7.10, 8.1, 8.9
 HW4(due Nov. 13): 8.2, 8.6, 8.8, 8.10 and 8.11
 HW5(due Dec. 2): 17.1, 17.2, 17.3, 17.4, and 17.5
Reading Assignments:
 Skim Introduction and Chapter 0,
Example 1.1,
Section 1.3.1, and
Section 1.6
 Read the proof of theorem 1.9 and sections 1.5.1, 1.52 (just for fun), and 3.3
 Read carefully Section 3.1 (special case of DTIME hierarchy theorem)
 Read carefully the proof of Theorem 4.18 (PATH is NLcomplete)