This course extends the basic course on computational complexity. It introduces the students to the concepts of
polynomial hierarchy classes, probabilistic computation, oracle computation, non-uniform computational
models and the PCP theorem.
Last update: T_KTI (28.04.2015)
Přednáška rozšiřuje základní přednášku o výpočetní složitosti. Seznamuje s třídami polynomiální hierarchie,
pravděpodobnostními výpočty, výpočty s orákuly, neuniformními modely výpočtu a PCP větou.
Aim of the course - Czech
Last update: T_KTI (23.05.2008)
Naučit další látku z teorie složitosti, třídy složitosti, jejich vlastnosti a vztahy.
Literature -
Last update: T_KTI (28.04.2015)
Arora S., Barak B. Computational Complexity: A Modern Approach. Cambridge University Press 2009
Balcázar, Díaz, Gabarró : Structural Complexity I, Springer Verlag 1988
Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press 2008
Last update: T_KTI (28.04.2015)
Arora S., Barak B. Computational Complexity: A Modern Approach. Cambridge University Press 2009
Balcázar, Díaz, Gabarró : Structural Complexity I, Springer Verlag 1988
Michal Černý, Výpočty I, II, III, Professional Publishing, 2011-2012
Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press 2008
V. Majerech: Složitost a NP-úplnost (skripta v elektronické podobě ke stažení na stránkách KTIML -