- 3.10.2017: Turing machines, time & space complexity, machines - languages - problems, Church-Turing thesis, random access machines, time vs. space, Sipser's theorem (statement only)
- 10.10.2017: Kolmogorov complexity, communication compexity, Sipser's theorem, constructible functions, universal machines
- 17.10.2017: hierarchy theorems, gap theorems, boolean circuits (basic definitions)
- 24.10.2017: machines vs circuits, machines with advice, uniform sequences of circuits, circuits of small depth (classes AC and NC), parity is not in AC0
- 31.10.2017: parity is not in AC0 (continued), extensions of AC0, nondeterministic Turing machines, a model with witnesses, classes of complements, NP intersected with coNP, determinization
- 7.11.2017: determinization, reachability in a directed graph and the Savitch theorem, reductions (Turing, Karp, Levin), complete problems for NP, P, polyL, L, NL
- 14.11.2017: PSPACE-completeness of QBF, Immerman-Szelepcseny theorem (NL=coNL), Ladner's theorem (NP-intermediate problems), dichotomy conjecture for CSP, Berman's theorem (single-letter alphabet vs NP)
- 21.11.2017: Berman's theorem (proof), relativization & the Baker-Gill-Solovay theorem, decision problems vs search problems, polynomial hierarchy, alternating machines
- 28.11.2017: alternating machines vs deterministic machines, probabilistic machines, class RP, amplification, examples of randomized algorithms: primality testing, checking that a polynomial is nonzero
- 5.12.2017: amplification for RP (a stronger variant), example randomized algorithm: perfect matchings, classes PP, BPP, ZPP (Las Vegas algorithms vs Monte Carlo algorithms), non-uniform derandomization (Adleman theorem), derandomization in practice
- 12.12.2017 - mid-term exam
- 19.12.2017: derandomization (pseudorandom generators & Yao's theorem); fixed-parameter tractability, treewidth, example: k-colorability, Courcelle's theorem; approximation (example: vertex cover)
- 9.01.2018: interactive proofs
- 16.01.2018: PCP
- 23.01.2018: approximation (continued), cryptography, one-way functions, pseudorandom generators, zero-knowledge proofs, quantum computations

See 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
**1.5 pt**. - The mid-term is worth
**1.5 pt**. The mid-term will be held on**12.12.2017**during the lecture, in room**4420**. - Everyone can approach the June exam (there is no lower limit for points from homeworks / mid-term).
- The final exam (first try) is worth
**3 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
**4.5 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: 1948