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.
Poslední úprava: T_KTI (26.04.2016)
This course extends the basic course on computational complexity (NTIN063). It covers hierarchy theorems for
probabilistic computation, time-space trade-offs for SAT, Toda's Theorem, pseudo-random generators and
interactive protocols.
Cíl předmětu
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.
Podmínky zakončení předmětu -
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
Ústní zkouška
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
Oral exam.
Literatura -
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: 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.
Požadavky ke zkoušce -
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: 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.
Sylabus -
Poslední úprava: T_KTI (26.04.2016)
Nedeterministická časová hierarchie a hierarchie pro pravděpodobnostní třídy výpočtů