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
