Složitost

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.