Plán  přednášek (bude průběžně aktualizován  dle  reality)

1. rekapitulace:  definice časové a prostorové složitosti, definice složitostní třídy, linear speedup, vztahy mezi složitostními třídami (determinizmus vs nedeterminizmus, čas vs prostor) [23.2.2017]
2.  uzávěrové vlastnosti složitostních tříd,  Immermanova - Szelepcsényiho věta [2.3.2017]
3.  separace složitostních tříd, hierarchie složitostních tříd  [9.3.2017]
4.  dolní odhady složitosti pro konkrétní jazyky, úplné a těžké problémy složitostních tříd [16.3.2017]
5.  NP úplnost, P úplnost[23.3.2017]
6.  úplnost ve třídách DLOG a NLOG   a PSPACE [30.3.2017]
7.  Turingova redukce; orákulový Turingův stroj a relativizované složitostní třídy, relativizace vztahu P a NP [6.4.2017]
8.  Polynomiální hierarchie. Alternující Turingův stroj [13.4.2017]
9.   Vztah alternujících a deterministických složitostních tříd, alternace a polynomiální hierarchie. Paralelizmus: logické obvody,  třída NC a její vztah k P, vysoce sekvenční problémy [20.4.2017]
10.  randomizace: TS s pravděpodobností, pravděpodobnostní složitostní třídy, vztah BPP a polynomiální hierarchie [27.4.2017]
11. interaktivní protokoly, vztah tříd PSPACE a IP 4.5.2017]
12. interaktivní protokoly, vztah tříd PSPACE a IP [11.5.2017]
13. přednáška se nekoná [18.5.2017]