Složitost
Témata přednásek
- 23: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)
- 1.3. - vztahy mezi složitostními třídami (dokončení), Savitchova věta, Immermanova - Szelepcsényiho věta
- 8.3. - deterministické a nedeterministické separace, hierarchie tříd
- 15.3: - definice složitostních tříd užitím certifikátu; úplné a těžké problémy složitostních tříd; NP-úplnost 3-zafarbení grafu
- 22.3: - NP-úplnost problémů Hamiltonovský cyklus a SubsetSum; P-úplnost problému CVP; PSPACE-úplnost slovního fotbalu
- 29.3. - úplnost ve třídách DLOG a NLOG; T-redukce; orákulový Turingův stroj a relativizované složitostní třídy
- 5.4: - relativizace vztahu P a NP; polynomiální hierarchie
- 12.4. - charakterizace tříd polynomiální hierarchie; definice alternujícího Turingova stroje
- 19.4. - vztah alternujících a deterministických složitostních tříd; logické obvody
- 26.4. - třída NC a její vztah k P, vysoce sekvenční problémy; TS s pravděpodobností, pravděpodobnostní složitostní třídy
- 3.5. - vztah BPP a polynomiální hierarchie, definice interaktivních protokolů
- 10.5. - vztah tříd PSPACE a IP
- 17.5. - dolní odhady složitosti - technika přechodových postupností