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

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

LS 2010/2011

TIN086 - 2/1 Z, Zk

Čas konání: Pá 12:20.
Místo konání: S6

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován ”klasičtějším“ partiím výpočetní složitosti. Ukázali bychom některé základní, dnes již prakticky klasické výsledky, např. Todovu větu (Polynomiální hierarchie vs. #P), větu Immermana a Szelepcsényiho (NL=coNL), Reingioldovu větu (SL=L), zmínili se o pravděpodobnostních výpočtech a pseudonáhodných generátorech (Nisanův PRG), a dále bychom se věnovali základům komunikační složitosti.

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

• Deterministická, nedeterministická časová a prostorová hierarchie, polynomiální hierarchie
• Izolační lemma
• Todova věta
• NL=coNL
• Pseudonáhodné generátory
• SL=L
• Komunikační složitost

Literatura:

• Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press 2008.
• Sanjeev Arora, Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press 2008. Verze na webu http://www.cs.princeton.edu/theory/complexity/
• Eyal Kushilevitz, Noam Nisan, Communication complexity, Cambridge University Press 1997.

Domácí úkoly

1. Do 1.4. 2011.
2. Do 22.4. 2011.
3. Do 20.5. 2011
4. Do do zkoušky.