Výpočetní složitost
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
ZS 2016/2017
NTIN082 - 2/0 Zk
Čas konání: St. 14:00-15:30. (První přednáška byla až 19.10. 2016)
Místo konání: S4, Malá Strana.
Přednáška rozšiřuje základní přednášku o výpočetní složitosti (NTIN063). Seznamuje s různými druhy booleovských obvodů a branching programů, jejich vzájemnými vztahy a vztahy s klasickými výpočetními třídami.
Přednáška je určena především
studentům magisterského studia a doktorandům. Přednáška
předpokládá základní znalosti z výpočetní složitosti,
pravděpodobnosti a diskrétní matematiky.
Plán přednášky
- Třída P/poly, Booleovské obvody.
- coNEXP součástí NEXP/poly (exponenciální verze NP vs coNP).
- NPNP nemůže mít Booleovské obvody velikosti O(nk) pro pevné k.
- Obvody logaritmické hloubky, Booleovské formule.
- Obvody konstantní hloubky.
- Parita není v AC0 - důkaz Razborova a Smolenského.
- Aproximace MAJ je v AC0.
- ACC0 vs CC0.
- Redukce hloubky obvodu.
- Williams: NEXP není v ACC0.
- Branching programy, vztah k logaritmickému prostoru.
- Barringtonova věta o vztahu branching programů k Booleovským formulím.
- Generalizace Barringtonovy věty: vyhodnocení aritmetické formule s použitím tří registrů.
- Katalytické výpočty.
Literatura: