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

Textbooks:
Grading
 Homeworks: 10% each (x6 = 60% total)
 Exams: 20% each (x2 = 40% total)
Tentative Course Schedule
 Monday, Sept 21: HW1 due
 Thursday, Oct 1: HW2 due
 Tuesday, Oct 13: HW3 due
 Thursday, Oct 15: Exam 1, in class
 [Friday, Oct 23: DROP DATE FOR FALL SEMESTER]
 Monday, Nov 2: HW4 due
 Tuesday, Nov 17: HW5 due
 Tuesday, Dec 1: HW6 due
 Thursday, Dec 3: Exam 2, in class
Lectures
 September 3, 2009: Course outline, introduction
[Slides]
 September 8, 2009: Turingmachine model, formal definitions of
polynomial time and nondeterministic polynomial time, manytoone
polynomialtime 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.
 September 10, 2009: Reducing SAT to 3SAT, start on proof of Cook's Theorem
 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
 September 17, 2009: The BakerGillSolovay Theorem
 September 22, 2009: Revisiting time constructibility, examples of
functions that are not timeconstructible; 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 spacebounded computation and
configuration graphs
 September 24, 2009: Savitch's Theorem; PSPACEcompleteness of TQBF
 September 29, 2009: Logspace reductions; NLcompleteness of PATH; The
ImmermanSzelepcsenyi Theorem
 October 1, 2009: Making Cook's reduction parsimonious; Introduction to the
PH
 October 6, 2009: Circuits and Turing Machines that take advice;
logspaceuniform circuits recognize exactly P; P/poly contains undecidable
languages; KarpLipton Theorem
 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)
 October 13, 2009: Review for Exam 1
 October 15, 2009: [Exam 1][Solutions]
 October 20, 2009: The SipserGacs Theorem; Introduction to IP;
Pairwiseindependent hashfunction families
 October 22, 2009: Proof that the set of all affine functions over a finite
field is a pairwiseindependent hashfunction family; the GoldwasserSipser
lowerbound protocol
 October 27, 2009: IP is contained in PSPACE, Arithmetization of 3CNF
formulae
 October 29, 2009: Interactive proof system for co3SAT
 November 3, 2009: Interactive proof system for TQBF
 November 5, 2009: More on the interactive proof system for TQBF.
Introduction to multiprover interactive proof systems.
 November 10, 2009: Using MIP = NEXP to prove a hardnessofapproximation
result for the cliquenumber problem. Introduction to #P.
 November 12, 2009: Proof of the USAT version of the ValiantVazirani
lemma; definition of parityP; amplification of correctness probability in
the parityP version of the ValiantVazirani lemma.
 November 17, 2009: Generalizing ValiantVazirani: 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
parityP.
 November 19, 2009: Derandomization to complete the proof of Toda's
Theorem: PH is contained in P^{#SAT}
 December 1, 2009: Review for Exam 2
 December 3, 2009: [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. You may also LaTex the problem
set nicely and email the pdf to the TA.
 HW1(due Mon, Sept 21): 1.2, 1.5, 1.15, 2.5, 2.10, 2.13, 2.30
 HW2(due Thurs, Oct 1): 3.2, 3.3, 3.6, 4.4, 4.6, 4.8, 4.10
 HW3(due Tues, Oct 13): 5.7, 5.9, 5.11, 6.3, 6.4, 6.9
 HW4(due Mon, Nov 2):7.6, 7.7, 7.10, 8.1, 8.9, 8.10
 HW5(due Tues, Nov 17): 8.7, 8.8, 17.1. 17.2, 17.3, 17.4
 HW6(due Tues, Dec 1): 6.14, 6.15, 7.9, 8.2, 8.5, 7.11 (optional)
Reading Assignments:
 Skim Introduction and Chapter 0
 Read sections 1.1, 1.2, 1.3, and 1.6
 Read discussion of Ladner's Theorem in Chapter 3
 Sections 7.6 and 7.7 of AroraBarak
 For HW5, read Sections 17.1, 17.2, and 17.3 of AroraBarak.