- 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

- Problems for tutorials
- Slides from the previous year
- Notes of D. NiwiĆski
- Notes of B. Klin
- A book Arora, Barak "Computational Complexity: A Modern Approach" (draft)
- Problem book (tutorials)
- Materials of M. Pilipczuk for tutorials: 2016/2017, 2015/2016
- Historical homeworks & exams

- 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.

Licznik: 5979