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

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

LS 2007/2008

TIN086 - 2/1 Z, Zk

Čas konání: čtvrtek 14:00-15:30.
Místo konání: S1 - Malá Strana

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ř. Toda's Theorem (Polynomiální hierarchie vs. #P), Immerman-Szelepcsényi's Theorem (NL=coNL), Reingiold's Theorem (SL=L), a dále pak bychom se věnovali interaktivním protokolům (AM, IP=PSPACE, MIP=NEXP, PCP věta).

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.
Todova věta.
NL=coNL.
SL=L.
Interaktivní protokoly - Arthur-Merlin (třída AM, IP=PSPACE).
Interaktivní protokoly s více dokazateli (MIP=NEXP).
NP=PCP(log n, 1).
Zero-knowledge proofs.

Literatura: Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach. 2008. Verze na webu http://www.cs.princeton.edu/theory/complexity/

Shrunti pravdepodobnosti.

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

Plán přednášky

Domácí úkoly