|
|
|
||
|
This course extends the basic course on computational complexity (NTIN063). It covers various types of Boolean
circuits and branching programs, their relationships and relationships to the usual complexity classes.
Last update: 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ů. Last update: T_KTI (26.04.2016)
|
|
||
|
The exam is oral. Last update: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)
|
|
||
|
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. Last update: T_KTI (26.04.2016)
|
|
||
|
he 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. Last update: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)
|
|
||
|
Boolean circuits and P/poly coNEXP is not in NEXP/poly NP^NP does not have circuit of size O(n^k), for fixed k Logarithmic depth circuit, Boolean formulas Constant depth circuits Parity not in AC0 - proofs of Razborov and Smolensky Approximating MAJ in AC0 ACC0 vs CC0 Circuit depth reductions Williams: NEXP is not in ACC0 Branching programs and their relationship to space bounded computation Barrington's Theorem Generalization of Barrington's Theorem for arithmetic formulas Catalytic computation Last update: T_KTI (26.04.2016)
|