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

Michal Koucký
<koucky@math.cas.cz>

ZS 2009/2010

TIN085 - 2/1 Z, Zk

Čas konání: Čt. 9:00 (první přednáška 8.9.)
Místo konání: chodba KTIML 3. patro, 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ť standartní 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 některé ze základních klasických výsledků a technik v této oblasti. 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.

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ůkazy Furst-Saxe-Sipsera a Razborov-Smolenského.
• Aproximace MAJ je v AC⁰.
• ACC⁰ vs CC⁰.
• Superkoncentrátory.
• Redukce hloubky obvodu.
• Dolní odhady pro Booleovské formule: metody Krapčenka a Nečiporuka.
• 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ů.

Literatura:

• 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.
• další články dle potřeby

Domání úkoly

1. Do 12.11. 2009.
2. Do 3.12. 2009.
3. Do 7.1. 2010.
4. Do zkoušky.