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: 
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
 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
 September 2, 2010: Course outline, introduction
[Slides]
 September 7, 2010: Turingmachine model,
Palindrome example, nondeterminism, running Time, timeconstructibility.
Thanks to Raonne Barbosa Vargas, who took
this course in 2008, we have this demo of a
Turing Machine recognizing a palindrome.
 September 9, 2010: Definitions of P, NP, manytoone polynomialtime reduction,
and NPcompleteness. Cook's Theorem.
 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 timeconstructible
 September 16, 2010: Oracle Turing Machines, the BakerGillSolovay Theorem.
 September 21, 2010: Spacebounded computation, configuration graphs, PATH is in NL, Savitch's Theorem.
 September 23, 2010: Logspace reductions, PATH is NLcomplete, the ImmermanSzelepcsenyi Theorem.
 September 28, 2010: TQBF is PSPACEcomplete, making Cook's reduction parsimonious
 September 30, 2010: The Polynomial Hierarchy (PH), Alternating Turing Machines
 October 5, 2010: Polynomialsized circuits, P is contained in P/poly, and the KarpLipton Theorem
 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 polynomialtime probabilistic computation.
 October 12, 2010: Review for Exam 1
 October 14, 2010: [Exam 1] [Solutions]
 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 SipserGacs Theorem (BPP is contained in the second level of the PH).
 October 21, 2010: Introduction to IP, Graph Nonisomorphism is in IP, Pairwiseindependent hashfunction families.
 October 26, 2010: ArthurMerlin games and the GoldwasserSipser lowerbound proof system. Probabilistic polynomialtime reductions, probabilistic spacebounded computation.
 October 28, 2010: Arithmetization of boolean formulas, coNP is contained in IP.
 November 2, 2010: IP is contained in PSPACE, multiprover interactive proof systems, "oracle proof systems," and checkers.
 November 4, 2010: IP=PSPACE, using MIP = NEXP to prove a hardnessofapproximation result for the cliquenumber problem.
 November 9, 2010: If GI is NPcomplete, then the PH collapses at the second level. The USAT version of the ValiantVazirani lemma.
 November 11, 2010: Definitions of #P and parityP, the parityP version of the ValiantVazirani lemma.
 November 16, 2010: The PH is in BPP^{parityP}.
 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.
 November 30, 2010: Review for Exam 2
 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.
 HW1 (due Tues, Sep 21): 1.2, 1.5, 1.15, 2.5, 2.13, 2.29, 2.30
 HW2 (due Thur, Sep 30): 3.3, 3.4, 4.4, 4.6, 4.8, 4.10, 3.6(EC)
 HW3 (due Tues, Oct 12): 5.7, 5.9, 5.10, 6.3, 6.4, 6.9
 HW4 (due Thur, Nov 4): 7.6, 7.7, 7.10, 8.9, 8.10, 8.11
 HW5 (due Tues, Nov 16): 7.9, 8.2, 8.5, 8.7, 8.8, 17.4, 7.11*
 HW6 (due Tues, Nov 30): 7.8, 8.1, 8.3, 8.12, 17.1
Reading Assignments:
 September 2, 2010: Skim Introduction and Chapter 0
 September 7, 2010: Read sections 1.1, 1.2, 1.3, and 1.6
 September 14, 2010: Read sections 1.5 and 1.7
 September 30, 2010: Read section 5.4
 October 7, 2010: Read sections 6.1.2 and 6.3
 November 9, 2010: Read sections 17.1, 17.2, and 17.3