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).
• 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 AC⁰ - důkaz Razborova a Smolenského.
• Aproximace MAJ je v AC⁰.
• ACC⁰ vs CC⁰.
• Redukce hloubky obvodu.
• Williams: NEXP není v ACC⁰.
• 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:

• Akualizované poznámky k přednášce.
• Stasys Jukna. Boolean Function Complexity: Advances and Frontiers.
• Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach. 2008. Verze na webu http://www.cs.princeton.edu/theory/complexity/
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press 2008.