Strukturální složitost
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
LS 2016/2017
NTIN081 - 2/0 Zk
Čas konání: Pá. 9:00-10:30
Místo konání: S6, Malá Strana.
Přednáška z 12.5. se přesouvá na středu 10.5. od 14:00-15:40 do S4.
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.