Strukturální složitost
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
LS 2018/2019
NTIN081 - 2/0 Zk
Čas konání: Po. 15:40-17:10
Místo konání: S4, Malá Strana
Přednáška navíc - pátek 25.5., v 10:40 v pracovně 360.
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ů.
- Polynomiální hierarchie a time-space trade-off pro SAT.
- Todova věta.
- NL=coNL.
- Pseudonáhodné generátory, Nisanův pseudonáhodný generátor.
- Interaktivní protokoly - Arthur-Merlin (třída AM, IP=PSPACE).
- 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.