Slides for the course "Complexity Theory"


These are my complete set of slides, around 20 lectures worth, of the graduate course "Complexity Theory". You are free to use these slides, but please refer to the source (this page, or the complexity course page). Email me if you would like the TeX source of these slides. You can download the entire set of slides in one pdf file here. Or listed by topic, they are:

Computation and Turing Machines: Turing machines, 3-tape TM for Palindromes, lower-bound for 1-tape TM for palindromes.
Universal Turing Machines and Undecidability: Dependence on number of tapes & alphabet size, Universal TMs, uncomputable functions, HALT undecidable.
The Class P: Definition of P, Boolean formulea, satisfiability, 2-CNF in P, reduction of 2-coloring to 2-CNF.
The Class NP: Certificate definition of NP, Non-deterministic TMs and equivalence to NP, polynomial-time reducibility.
The Cook-Levin Theorem: Relation between Boolean functions and satisfiability, Cook-Levin theorem, CNF reducible to 3-CNF.
NP hardness Reductions: NP-hardness reductions for Independent set, Vertex-cover, Integer Programming.
Further NP hardness Reductions: NP-hardness reductions for Hamiltonian cycle and Knapsack problem.
Search vs Decision and coNP: Decision vs. optimization, coNP, relation between NP and coNP.
Space Complexity 1: Definition of space complexity, PSPACE, relation to NP & DTIME, Quantified Boolean Formulas (QBF), QBF is in PSPACE.
Space Complexity 2: Proof of SPACE(o(loglogn)) = SPACE(O(1)), Nondeterministic space complexity.
Nondeterministic Space Complexity: Reachability in NSPACE(log n) & SPACE(log^2 n), Savitch's theorem, Class L & its certificate definition, log-space reductions.
Complement Space Complexity: coPSPACE & coNL, Proof of Immerman-Szelepscenyi theorem.
The Polynomial Hierarchy: Properties of class &sum 2, polynomial hierarchy, P=NP implies collapse of PH, complete problems for PH, defining PH via oracle TMs, TISP.
Randomized Computation 1: Polynomial identity testing, probabilistic TMs, classes RP, coRP, BPP & ZPP, boosting probabilities.
Randomized Computation 2: Proof of ZPP = RP &cap coRP, proof of BPP = &sum 2
Interactive Proofs: Deterministic proof systems, equivalence to NP, interactive proof systems, authentication without giving password, IP for graph non-isomorphism.
Interactive Proofs: co3SAT: Proof of co3SAT is in IP.
Interactive Proofs: IP = PSPACE : Proof of #SAT is in IP, sketch of proof of IP=PSPACE theorem.
Probabilistically Checkable Proofs: 7/8-approximation for 3-SAT, probabilitically checkable proofs, PCP(logn, poly(n)) ⊆ NP, gap-producing functions & PCP theorem.