Sylabus
1) Turingovy stroje s orákulem.
2) Polynomiální hierarchie (definice pomocí orákulí a pomocí alternujicích kvantifikátorů, důkaz ekvivalence).
3) Kvantifikované booleovské formule QBF a jejich úplnost pro PSPACE a Σi.
4) Nedeterministická hierarchie.
5) Log-space převoditelnost, P-úplnost a její důsledky.
6) Věta Szelepcsenyi-Immermana a NL=coNL.
7) Neuniformní výpočetní modely - radicí funkce, booleovské obvody, třídy NC a P/poly, funkce s maximální velikostí obvodu.
8) Pravděpodobnostní algoritmy - třídy RP, coRP, ZPP a BPP.
9) Redukce chyby pro BPP, BPP je v P/poly, BPP je v Σ2.
10) NP-úplnost UNIQUE-SAT (pravděpodobnostní redukce)
11) PCP věta (bez důkazu) a její využití pro neaproximovatelnost.
Anotace
Přednáška rozšiřuje základní přednášku o výpočetní složitosti. Seznamuje s třídami polynomiální hierarchie, pravděpodobnostními výpočty, výpočty s orákuly, neuniformními modely výpočtu a PCP větou.