Tentative Topics

Turing Machines review

P v NP

SAT is NP-complete

Ladner's Theorem

Mahaney's Theorem

Relativization - Why P v NP is hard

Alternation and PSPACE

Polynomial-Time Hierarchy

P/poly, Karp-Lipton

Circuit Complexity

Razborov-Smolensky

Time-Space Tradeoffs for SAT

Randomness:
RP, co-RP, BPP, ZPP

BPP in Polynomial-time hierarchy

Arthur-Merlin Games and Graph Non-Isomorphism

Public v Private Coins

Counting Complexity

Permanent

Toda's theorem

IP = PSPACE

PCP theorem

Quantum Computing