|
|
|
||
Poslední úprava: T_KTI (26.04.2016)
|
|
||
Poslední úprava: T_KTI (26.04.2016)
Naučit další látku z teorie složitosti zejména v oblasti neuniformních výpočetních modelů. |
|
||
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
Zkouška je ústní. |
|
||
Poslední úprava: T_KTI (26.04.2016)
Stasys Jukna. Boolean Function Complexity: Advances and Frontiers.
Sanjeev Arora, Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press 2008.
Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press 2008. |
|
||
Poslední úprava: prof. Mgr. Michal Koucký, Ph.D. (10.06.2019)
Zkouš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)
Třída P/poly, Booleovské obvody coNEXP součástí NEXP/poly (exponenciální verze NP vs coNP) NP^NP nemůže mít Booleovské obvody velikosti O(n^k) pro pevné k Obvody logaritmické hloubky, Booleovské formule Obvody konstantní hloubky Parita není v AC0 - důkaz Razborova a Smolenského Aproximace MAJ je v AC0 ACC0 vs CC0 Redukce hloubky obvodu Williams: NEXP není v ACC0 Branching programy, vztah k logaritmickému prostoru Barringtonova věta o vztahu branching programů k Booleovským formulím Generalizace Barringtonovy věty: vyhodnocení aritmetické formule s použitím tří registrů Katalytické výpočty |