Obsah přednášek

Realita

• 19.2.    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)
• 26.2.     vztahy mezi složitostními třídami (Savitchova věta), Immermanova - Szelepcsényiho věta
• 5.3.       deterministické a nedeterministické  separace
• 12.3.     hierarchie tříd, dolní odhady složitosti pro konkrétní jazyky, úplné a těžké problémy složitostních tříd, NP úplnost
• 19.3.     NP-úplnost problémů splnitelnosti,  3-zafarbení grafu, Hamiltonovský cyklus a SubsetSum; PSPACE-úplnost TQBF a slovního fotbalu
• 26.3.    úplnost ve třídách DLOG a NLOG; definice složitostních tříd užitím certifikátu, T-redukce; orákulový Turingův stroj a relativizované složitostní třídy
• 2.4.      Turingova redukce (orákulové Turingove stroje), relativizace vztahu P a NP
• 9.4.       polynomiální hierarchie, charakterizace tříd polynomiální hierarchie
• 16.4.     přednáška se nekoná
• 23.4.     definice alternujícího Turingova stroje, vztah alternujících a deterministických složitostních tříd; logické obvody
• 30.4.     třída NC a její vztah k P, vysoce sekvenční problémy; TS s pravděpodobností, pravděpodobnostní složitostní třídy
• 7.5.       vztah BPP a polynomiální hierarchie, definice interaktivních protokolů
• 14.5.     vztah tříd PSPACE a IP