Computational complexity 2019/2020
The official language of this course is English.
Summary of lectures
- 8.10.2019: Turing machines; Church-Turing thesis; (semi)decidability; halting property; time complexity; random access machines
- 15.10.2019: nondeterministic Turing machines; a model with witnesses; classes NP, coNP, NP∩coNP; reductions (Turing, Karp, Levin)
- 22.10.2019: NP-complete problems; Ladner's theorem (problems between P and NP-complete)
- 29.10.2019: CSP dichotomy; Berman's theorem (difficult languages that are not NP-hard); decision problems vs search problems; space complexity
- 5.11.2019: determinisation; Sipser's theorem (removing loops); TQBF is PSPACE-complete; Savitch theorem
- 12.11.2019: hierarchy theorems, gap theorems
- 19.11.2019: relativization & the Baker-Gill-Solovay theorem; polynomial hierarchy
- 26.11.2019: log-space reductions; reachability is NL-complete; Horn-SAT is P-complete; NL=coNL; Boolean circuits (polynomial size, log-space uniform)
- 3.12.2019: Boolean circuits (equivalence between machines and circuits, class P/poly, circuits of small depth = parallel algorithms)
- 10.12.2019: mid-term exam
- 17.12.2019: probabilistic algorithms: classes BPP & RP; examples (primality, equality of polynomials, perfect matching)
- 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
- 14.01.2019: approximation (vertex cover, TSP, knapsack), PTAS; fixed-parameter tractability, tree width
- 21.01.2019: interactive proofs, IP=PSPACE
Homeworks (series 1, 2a, 2b, 3): see here
- Homeworks are worth 36 pt.
- The mid-term is worth 24 pt.
The mid-term will be held on 10.12.2019 during the lecture, in room 4420, at 12:00.
- Everyone can approach the exam (there is no lower limit for points from homeworks / mid-term).
- The final exam (first try) is worth 40 pt.
- The first-term grade encompasses the sum of points from the homeworks, the mid-term, and the exam.
- The final exam (second try) is worth 64 pt.
- The second-term grade encompasses the sum of points from the homeworks and the exam.
- The exam (both terms) consists of two parts: the theory, and the practice.
- All solutions (homeworks, mid-term, exam) should be written in English.