Complexity Theory 2016

News | Dates | Grading | Content | Exercises | Exam | Material

This lecture requires basic knowledge in automata theory and theoretical computer science. No specific knowledge on complexity theory is required, because all basic ideas will be recapitulated.

The course is roughly based on the book Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. A draft version (containing several errors) is accessible online here

Another classical text on complexity theory is Computational Complexity by Christos H. Papadimitriou.

Syllabus

Covered in a Previous Class (minor deviations possible)

1. introduction: tractability vs. intractability, independent set, three-coloring, reductions, efficiently checkable certificates
2. Turing machines: definition, TM for palindromes, robustness, universal TMs
3. computability and halting problem, non-deterministic TM, decisions vs. search problems, definition of basic TIME and SPACE classes: L, NL, P, NP, PSPACE, EXP
4. NP = polynomially checkable certificates, Karp reductions, definition hardness, completeness, Cook-Levin theorem
5. Cook-Levin Theorem proof; NP-completeness of 0/1-ILP, independent set and 3-coloring by reductions from 3SAT; SAT tool demo
6. coNP, coNP-completeness, certificate characterization, Tautology and star-free reg. expression equivalence are coNP-complete, P vs NP vs coNP, Ladner's theorem
7. Ladner's theorem, time hierarchy theorem, space hierarchy theorem, configuration graphs, relations between space and time classes
8. PSPACE, quantified boolean formulas and generalized geography are PSPACE-complete, reduction from QBF to GG, on succinctness, PSPACE=NPSPACE and Savitch's theorem, PSPACE and winning strategies
9. NL, Path is NL-complete, Immerman-Szelepcsenyi (NL=coNL), 2SAT is in NL
10. exact Indset, polynomial hierarchy, k-bounded QBF complete for each level k, integer expressions, If P=NP then PH=P
11. TISP(t,s): simultaneous time and space; Fortnow's result: SAT not in TISP(n^1.1, n^0.1)
12. probabilistic TMs, RP, coRP, ZPP, BPP, PP
13. probabilistic TMs, RP, coRP, ZPP, BPP, PP
14. introduction to interactive proofs, prover vs verifier, socks example, zero-knowledge proof for graph colorability, graph NON-isomorphism, definition and basic properties of IP, AM, IP[k], AM[k], error reduction by sequential repetition
15. Arthur-Merlin protocols, AM[2] protocol for graph non-isomorphism, Goldwasser-Sipser set lower bound protocol, GI NP-complete implies that the hierarchy collapses
16. IP contains PSPACE by showing interactive protocol for QBF, arithmetization of Boolean formulas, linearization for quantified case
17. IP is contained in PSPACE because optimal provers can be computed in PSPACE, proof of improbability of NP-completeness of graph isomorphism
18. approximation for vertex cover (2), set cover (ln n), and metric/geographic TSP (2, minimum spanning tree+DFS), gap-TSP, gap-TSP[|V|,h|V|] is NP-hard for all h>1
19. PCP (hardness of approximation), gap-3SAT, gap-producing and gap-preserving reductions; NP-hardness of approximating Indset to within any 0 probabilistically checkable proofs, PCP(poly,1) system for graph non-isomorphism, PCP(r,q) definition, PCP theorem: NP=PCP(log,1), equivalence of PCP theorem with existence of a gap-producing reduction to qCSP
20. proof of NP contained in PCP(poly,1) using Walsh-Hadamard encodings of strings
21. PRAM with CRCW/CREW/EREW, efficient parallel computation robust under PRAM variations, definition of circuits and circuit families, logspace-uniformity, circuit depth<->parallel computation time, circuit size<->number of PRAM processors, def of NC and AC
22. NC1 in L in NL in NC2 in NC=AC in P
23. Parity is not in AC0, Haastads Switching Lemma, random restrictions