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 -
Last update: prof. RNDr. Ondřej Čepek, Ph.D. (26.09.2020)
The aim is to learn more advanced topics from the complexity theory, complexity classes, their properties and mutual relations.
Last update: T_KTI (23.05.2008)
Naučit další látku z teorie složitosti, třídy složitosti, jejich vlastnosti a vztahy.
Course completion requirements -
Last update: RNDr. Petr Kučera, Ph.D. (30.04.2020)
Credit is given for solving enough homework assignments. The lecture is finished with an oral exam. Depending on the situation, it is possible that the exam can proceed remotely.
Last update: RNDr. Petr Kučera, Ph.D. (30.04.2020)
K udělení zápočtu je třeba vyřešit dostatečné množství domácích úkolů. Předmět bude zakončen ústní zkouškou, která může s ohledem na situaci probíhat i distančně.
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 -