|
|
|
||
Last update: T_KTI (26.04.2016)
|
|
||
Last update: 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. |
|
||
Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
Oral exam. |
|
||
Last update: 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. |
|
||
Last update: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
The exam is oral from the material covered by the lectures. Each student gets reasonable time (at most three hours) for preparation upon receiving the questions.
Study materials (lecture notes, text books, etc.), computers and other electronic devices are not allowed during the exam. |
|
||
Last update: T_KTI (26.04.2016)
Nondeterministic time hierarchy and hierarchy for probabilistic computation BPP and polynomial hierarchy Time-space trade-off for SAT Isolation Lemma and Toda's Theorem Pseudo-random generators, Nisan's pseudo-random generator Interactive protocols - Arthur-Merlin games (class AM, IP=PSPACE) Multi-prover interactive protocols (MIP=NEXP) |