CPS 240: Computational Complexity

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]
8 Feb 6 Nondeterministic space
Reducibilities: many-to-one, 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
NP-Completeness: Examples and Reductions
[Pap, Ch8,9]
[HU, Ch13]
[GJ, Ch3]
11 Feb. 18 NP-Completeness: Cook's Theorem
Characterizations of NP
[Pap, Ch9]
[HU, Ch13]
[GJ, Ch3,4]
12 Feb. 20 PSPACE: QBF, Motion Planning
First Order Theories
Cook's theorem
[Pap, Ch19]
[HU, Ch13]
13 Feb. 25 Alternating TM [CKS] [Pap, Sec16.2]
14 Feb. 27 Alternating TM
Polynomial Hierarchy
[Pap, Ch17]
15 March 4 Polynomial Hierarchy [Pap, Ch17]
16 March 6 Counting Problems
[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
[Pap, 11]
20 April 8 BPP, circuit complexity, & PH
One-way functions, public-key cryptography
HW4 [Pap 11, 17, 18]
[Pap 12]
21 April 11 One-way functions, public-key cryptography
RSA system
Interactive protocols
[Pap 12]
22 April 15 Interactive protocols, IP
Intercative protocol for #P
[L, Ch3] [Pap 19]
23 April 17 PCP and approximability [ACGK, Ch6] [ACGK Ch6]
24 April 22 PCP theorem [HPS] [ACGK Ch7]

Relevant References

History of Computing and Complexity Theory

Turing Machines

Complexity Theory: Early Papers


First Order Theories




Agarwal's Home Page

Return to CPS240 Homepage