NTIN049 - Pravděpodobnostní důkazy a NP-úplnost
  ZS 2008

Zajišťuje: KAM
Vyučující: Jiří Sgall
Rozsah v ZS: 2/0 Zk
Rozsah v LS: ----

Anotace

Cílem přednášky je podat úplný důkaz slavné PCP věty z roku 1992 a jejích důsledků, s mírnými exkurzemi do souvisejících oblastí. Tato věta patří k nejdůležitějším výsledkům teoretické informatiky v poslední době zejména díky dalekosáhlým důsledkům o obtížnosti i příbližného řešení NP-úplných úloh.

Osnova

Úlohy patřící do třídy NP (jako třeba test, zda výroková formule je splnitelná) mají tu vlastnost, že kladnou odpověď je možné prokázat krátkým důkazem (v daném příkladu splňujícím ohodnocením). Takzvaná PCP věta říká, že pro každou úlohu v NP existuje dokonce způsob, jak kladnou odpověď prokázat čtením pouze konstantně mnoha (např. 20) náhodně vybraných bitů z celého důkazu, přičemž pravděpodobnost chyby je malá konstanta.

Tato věta dokázaná v r. 1992 patří k nejdůležitějším výsledkům teoretické informatiky v poslední době zejména díky dalekosáhlým důsledkům o obtížnosti i příbližného řešení NP-úplných úloh. Technicky věta souvisí s mnoha zajímavými oblastmi, např. opravné kódy, kryptografie, konečná tělesa, polynomy nízkého stupně v mnoha proměnných, ověřování algebraických identit, expandery, atd.

Cílem přednášky je podat úplný důkaz PCP věty a jejích důsledků, s mírnými exkurzemi do souvisejících oblastí. Přednáška je určena především studentům vyšších ročníků a doktorandům. Předpokládá se znalost základních pojmů ze složitosti.

Základní lit.

Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach
http://www.cs.princeton.edu/theory/index.php/Compbook/Draft

J. Sgall: Probabilistic Proofs and NP-completeness (A Course on the PCP Theorem and its Consequences). ITI series 2002-088.

Doplň. popis

Přednáška se nekoná každý rok, předpokládám její opakování za 2-3 roky. 

Úmluva bude v prvním týdnu semestru na KAM, v rámci hromadné úmluvy na výběrové přednášky KAM. 
Kontakt: sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 222 090 780.

24. 9. 2008