Neuniformní výpočetní modely

ZS 2025/2026
NTIN082 - 2/0 Zk

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

Čas konání: St. 9:00-10:30
Místo konání: S8, Malá Strana.

Přednáška rozšiřuje základní přednášku o výpočetní složitosti (NTIN063). Seznamuje s různými druhy booleovských obvodů a branching programů, jejich vzájemnými vztahy a vztahy s klasickými výpočetními třídami.

Přednáška je určena především studentům magisterského studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky.

Plán přednášky

• 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 AC⁰ - důkaz Razborova a Smolenského.
• Aproximace MAJ je v AC⁰.
• ACC⁰ vs CC⁰.
• Redukce hloubky obvodu.
• Williams: NEXP není v ACC⁰.
• 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.

Lectures

• 18.3.2020 - Alternating computation, SAT, TAUT, QBF.
• 25.3.2020 - QBF is PSPACE-complete, oracle computation.
• 8.4.2020 - Karp-Lipton Theorem, Collapse of PH.
• 15.4.2020 - NC^1 circuits and Boolean formulas.
• 22.4.2020 - AC^0 circuits.
• 29.4.2020 - Razborov-Smolensky: PARITY not in ACC0.
• 6.5.2020 - Razborov-Smolensky (end), APPROX-MAJ in AC0
• 13.5.2020 - Decission trees and branching programs
• 20.5.2020 - Ben-Or and Cleve construction

Literatura:

• Akualizované poznámky k přednášce ZS 2016/2017 & 2022.
• Stasys Jukna. Boolean Function Complexity: Advances and Frontiers.
• Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach. 2008. Verze na webu http://www.cs.princeton.edu/theory/complexity/
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press 2008.
• Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, Vol. 288(1), pp. 21-43, 2002.