# Computational complexity 2019/2020

[up]
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

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