Lect.  Date  Topics  Handouts  Reading 

1  Jan. 9  Introduction, History of computing  Synopsis  [Pap, Ch1] 
2  Jan. 16  Turing machines, decidability  [Pap, Ch2]
[HU, Ch7] 

3  Jan. 21  Turing machine: tape reduction
linear speed up 
[Pap, Ch2]
[HU, Ch12] 

4  Jan. 23  Nondeterminism, NTM vs DTM,
time complexity, universal TM 
[Pap, Ch2,3]
[HU, Ch7,12] 

5  Jan. 28  Halting problem, computability,
primitive recursive function 
HW1  [Pap, Ch3]
[HU, Ch8] 
6  Jan. 30  Complexity measures
Space vs time complexity hierarchy theorems 
[Pap, Ch7]
[HU, Ch12] 

7  Feb. 4  Complexity classes, Reachability
Savitch's theorem 
[Pap, Ch7] [HU,12] 

8  Feb 6  Nondeterministic space
Reducibilities: manytoone, truthtable, Turing Oracle TMs 
[Pap, Ch7,8]
[Pap, Sec14.3] 

9  Feb 11  Reducibilities: Examples
Relations between reducibilities Transitive and closure properties 
HW2  [Pap, Ch8] 
10  Feb. 13  Hard and Complete Languages NPCompleteness: Examples and Reductions 
[Pap, Ch8,9]
[HU, Ch13] [GJ, Ch3] 

11  Feb. 18  NPCompleteness: Cook's Theorem Characterizations of NP CoNP 
[Pap, Ch9]
[HU, Ch13] [GJ, Ch3,4] 

12  Feb. 20  PSPACE: QBF, Motion Planning EXP, NEXP, EXPSPACE First Order Theories 
Reducibilities
Cook's theorem 
[Pap, Ch19]
[HU, Ch13] 
13  Feb. 25  Alternating TM  [CKS]  [Pap, Sec16.2]
[CKS] 
14  Feb. 27  Alternating TM
Polynomial Hierarchy 
HW3  [CKS] [Pap, Ch17] 
15  March 4  Polynomial Hierarchy  [Pap, Ch17]  
16  March 6 
Counting Problems
#P 
[Pap, Ch18]  
March 11,13  Spring Break  
March 18  Midterm  
March 20,25  Class Cancelled  
17  March 27 
Circuit complexity, uniform vs nonuniform
Lower bounds on size 
[Pap, 11.4]  
18  April 1  Montone circuits, Razborov's theorem  [Pap, 14.4]  
19  April 3 
Randomized complexity, Probabilistic TM
RP, ZPP, PP, BPP 
[Pap, 11]  
20  April 8 
BPP, circuit complexity, & PH
Oneway functions, publickey cryptography 
HW4 
[Pap 11, 17, 18]
[Pap 12] 
21  April 11 
Oneway functions, publickey cryptography
RSA system Interactive protocols 
[Pap 12]  
22  April 15 
Interactive protocols, IP
Intercative protocol for #P IP=PSPACE 
[L, Ch3] 
[Pap 19]
[Handout] 
23  April 17  PCP and approximability  [ACGK, Ch6]  [ACGK Ch6] 
24  April 22  PCP theorem  [HPS] 
[ACGK Ch7]
[HPS] 
Return to
CPS240 Homepage