Vybrané kapitoly z výpočetní složitosti II

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

LS 2013/2014

TIN086 - 2/1 Z, Zk

Dne 14.5.2014 přednáška odpadá z důvodů rektorského dne.

Čas konání: St 9:00.
Místo konání: S8, Malá Strana.

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován tzv. neuniformním výpočetním modelům. Centrální otázka ve složitosti je "P vs. NP". Nikdo neví, jak ji řešit, neboť standardní model výpočtů, Turingův stroj, se tězko analyzuje. Za tímto účelem byly zavedeny modely jako Booleovské obvody, Booleovské formule a branching programy, které lze analyzovat kombinatoricky či algebraicky. V tomto semestru ukážeme jak některé ze základních klasických výsledků a technik, tak některé nejnovější výsledky jako je výsledek Williamse, pojem transparentních výpočtů apod.

Přednáška je určena především studentům vyšších ročníků 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. Přednášku je možné si zapsat opakovaně.

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/
• Dieter van Melkebeek. Complexity Theory. 2007. Lecture notes.

• Eric Allender. CS198:540 - Combinatorial Methods in Complexity Theory. Lecture notes Number 7 and Number 8.
• Ryan Williams. Non-Uniform ACC Circuit Lower Bounds, Journal of the ACM 61(1), Article 2 (January 2014).
• H. Buhrman, E. Cleve, M. Koucký, B. Loff, F. Speelman. Computing with a full memory: Catalytic space, 46th Annual ACM Symposium on Theory of Computing, STOC 2014.

• další články dle potřeby

Domácí úkoly

1. Do 26.3. 2014.
2. Do 30.4. 2014.
3. Do do zkoušky.