|
|
|
||
|
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)
|
|
||
|
The aim is to learn more advanced topics from the complexity theory, complexity classes, their properties and mutual relations. Last update: Čepek Ondřej, prof. RNDr., Ph.D. (26.09.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: Kučera Petr, RNDr., Ph.D. (30.04.2020)
|
|
||
|
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)
|
|
||
|
1) Oracle Turing machines. 2) Polynomial hierarchy (definitions based on oracles and on alternating quantifiers, proof of their equivalence) 3) Quantified boolean formulas QBF and their completenes for PSPACE and Σi. 4) Nondeterministic hierarchy theorems. 5) Log-space reducibility, P-completeness and its consequences. 6) Szelepcsenyi-Immerman theorem, NL=coNL. 7) Non-uniform computational models - advice functions, boolean circuits, classes NC and P/poly, functions with maximum circuit size. 8) Probabilistic algorithms - classes RP, coRP, ZPP, and BPP. 9) Error reduction in BPP, BPP is in P/poly, BPP is in Σ2. 10) NP-completeness of UNIQUE-SAT (probabilistic reduction) 11) PCP theorem (without proof) and its applications in inaproximability. Last update: T_KTI (28.04.2015)
|
|
||
|
TBA Last update: Hric Jan, RNDr. (07.06.2019)
|