|
|
|
||
Poslední úprava: T_KTI (26.04.2016)
|
|
||
Poslední úprava: T_KTI (26.04.2016)
Naučit další látku z teorie složitosti: vztahy mezi třídami složitosti, pseudonáhodné generátory a interaktivni protokoly. |
|
||
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
Ústní zkouška |
|
||
Poslední úprava: T_KTI (26.04.2016)
Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press 2008.
Sanjeev Arora, Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press 2008.
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 EATCS, 73: 57-77, 2001. |
|
||
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
kouška je ústní. Zkouší se z probrané látky. Po zadání otázek dostane student čas na přípravu.
Studijní materiály (skripta, učebnice a zápisky z přednášek) ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny. |
|
||
Poslední úprava: T_KTI (26.04.2016)
Nedeterministická časová hierarchie a hierarchie pro pravděpodobnostní třídy výpočtů BPP a polynomiální hierarchie Time-space trade-off pro SAT Izolační lema a Todova věta 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)
|