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

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

ZS 2015/2016

TIN085 - 2/1 Z, Zk

Čas konání: Pondělí, 9:00.
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.

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

• 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:

• 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.

Domácí úkoly

1. Do 23.11. 2015.
2. Do 14.12. 2015.
3. Do 11.1. 2016