Výpočetní složitost

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

LS 2019/2020

NTIN082 - 2/0 Zk

Čas konání: Wednesday 10:40-12:10.
Místo konání: Via Zoom https://matfyz.zoom.us/j/4042155019, 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.

Lectures

18.3.2020 - Alternating computation, SAT, TAUT, QBF.
25.3.2020 - QBF is PSPACE-complete, oracle computation.
8.4.2020 - Karp-Lipton Theorem, Collapse of PH.
15.4.2020 - NC^1 circuits and Boolean formulas.
22.4.2020 - AC^0 circuits.
29.4.2020 - Razborov-Smolensky: PARITY not in ACC0.
6.5.2020 - Razborov-Smolensky (end), APPROX-MAJ in AC0
13.5.2020 - Decission trees and branching programs
20.5.2020 - Ben-Or and Cleve construction

Literatura:

Akualizované poznámky k přednášce ZS 2016/2017.
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.