Sylabus
Třída P/poly, Booleovské obvody coNEXP součástí NEXP/poly (exponenciální verze NP vs coNP)
NP^NP nemůže mít Booleovské obvody velikosti O(n^k) 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
Anotace
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.