Výpočetní složitost a interaktivni protokoly

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

LS 2022/2023

NTIN081 - 2/0 Zk

Čas konání: Út. 14:00-15:30. (První přednáška 21.2.2023.)
Místo konání: S321 (chodba 3. patro), Malá Strana.
Jazyk: česky nebo anglicky dle požadavku studentů (taught in Czech or English depending on students)

Přednáška rozšiřuje základní přednášku o výpočetní složitosti (NTIN063). Seznamuje s hierarchií pro pravděpodobnostní třídy výpočtů, time-space trade-offs pro SAT, Todovou větou, pseudonáhodnými generátory a interaktivními protokoly.

Přednáška je určena především studentům magisterského studia a doktorandům.

Plán přednášky

Nedeterministická časová hierarchie a hierarchie pro pravděpodobnostní třídy výpočtů (Notes: Universal Turing Machines, Hierarchy theorems.)
BPP a polynomiální hierarchie (Notes: BPP and Polynomial Hierarchy)
Time-space trade-off pro SAT (Notes: Time-space trade-off for SAT)
Izolační lema a Todova věta (Notes: Isolation Lemma and Toda's Theorem)
Pseudonáhodné generátory, Nisanův pseudonáhodný generátor (Notes: Pseudorandom generators and Nisan's PRG)
Interaktivní protokoly - Arthur-Merlin (třída AM, IP=PSPACE) (Notes: Interactive proof systems)
Interaktivní protokoly s více dokazateli (MIP=NEXP)

Literatura:

Akualizované poznámky k přednášce.
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.
D. van Melkebeek and K. Pervyshev. A Generic Time Hierarchy for Semantic Models With One Bit of Advice. Computational Complexity, 16: 139-179, 2007.
D. van Melkebeek. Time-Space Lower Bounds for Satisfiability. Bulletin of the European Association for Theoretical Computer Science, 73: 57-77, 2001.