Předběžný časový plán (postupně bude aktualizován podle reality)

• 21:2: -  definice časové a prostorové složitosti, definice složitostní třídy, linear speedup, vztahy mezi složitostními třídami (determinizmus vs nedeterminizmus, cas vs prostor)
• 28.2.   -  vztahy mezi složitostními třídami (dokončení), Immermanova - Szelepcsényiho věta
• 7.3.  - Savitchova věta, deterministické separace
• 14.3. xxxx
• 21.3: - nedeterministické separace, hierarchie tříd, definice složitostních tříd užitím certifikátu; úplné a těžké problémy složitostních tříd
• 28.3: - NP-úplnost problémů 3-zafarbení grafu, Hamiltonovský cyklus a SubsetSum; P-úplnost problému CVP; PSPACE-úplnost slovního fotbalu
• 4.4. - úplnost ve třídách DLOG a NLOG; T-redukce; orákulový Turingův stroj a relativizované složitostní třídy
• 11.4: - relativizace vztahu P a NP; polynomiální hierarchie
• 18.4. - charakterizace tříd polynomiální hierarchie
• 25.4. - definice alternujícího Turingova stroje, vztah alternujících a deterministických složitostních tříd; logické obvody
• 2.5. - třída NC a její vztah k P, vysoce sekvenční problémy; TS s pravděpodobností, pravděpodobnostní složitostní třídy
• 9.5. -   vztah BPP a polynomiální hierarchie, definice interaktivních protokolů
• 16.5. - vztah tříd PSPACE a IP
• %. - dolní odhady složitosti - technika přechodových postupností