Computational complexity 2019/2020

The official language of this course is English.

Summary of lectures

  1. 8.10.2019: Turing machines; Church-Turing thesis; (semi)decidability; halting property; time complexity; random access machines
  2. 15.10.2019: nondeterministic Turing machines; a model with witnesses; classes NP, coNP, NP∩coNP; reductions (Turing, Karp, Levin)
  3. 22.10.2019: NP-complete problems; Ladner's theorem (problems between P and NP-complete)
  4. 29.10.2019: CSP dichotomy; Berman's theorem (difficult languages that are not NP-hard); decision problems vs search problems; space complexity
  5. 5.11.2019: determinisation; Sipser's theorem (removing loops); TQBF is PSPACE-complete; Savitch theorem
  6. 12.11.2019: hierarchy theorems, gap theorems
  7. 19.11.2019: relativization & the Baker-Gill-Solovay theorem; polynomial hierarchy
  8. 26.11.2019: log-space reductions; reachability is NL-complete; Horn-SAT is P-complete; NL=coNL; Boolean circuits (polynomial size, log-space uniform)
  9. 3.12.2019: Boolean circuits (equivalence between machines and circuits, class P/poly, circuits of small depth = parallel algorithms)
  10. 10.12.2019: mid-term exam
  11. 17.12.2019: probabilistic algorithms: classes BPP & RP; examples (primality, equality of polynomials, perfect matching)
  12. 7.01.2019: classes PP, ZPP (Las Vegas algorithms vs Monte Carlo algorithms); non-uniform derandomization (Adleman theorem); derandomization in practice; pseudorandom generators & Yao's theorem
  13. 14.01.2019: approximation (vertex cover, TSP, knapsack), PTAS; fixed-parameter tractability, tree width
  14. 21.01.2019: interactive proofs, IP=PSPACE


Homeworks (series 1, 2a, 2b, 3): see here


Grading Rules

Licznik: 5979

Valid HTML 4.0!