Neuniformním výpočetní modely

LS 2024
NTIN082 - 2/0 Zk

Pavel Hrubeš
<pahrubes@gmail.com>

Čas konání: Ut. 10:40-12:10
Místo konání: S1, 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ů, branching programů, a aritmetických obvodů. Ukážeme vztahy mezi těmito obvody a základními složitostními třídami a klasické dolní odhady na velikost obvodů.

Přednáška je určena především studentům magisterského studia a doktorandům.

Plán přednášky

• Třída P/poly, Booleovské obvody.
• Booleovské formule.
• Obvody konstantní hloubky.
• Parita není v AC⁰ - důkaz Razborova a Smolenského.
• Monotónní obvody, vztah k velikosti resolučních důkazů.
• Branching programy, vztah k logaritmickému prostoru.
• Barringtonova věta o vztahu branching programů k Booleovským formulím.
• Aritmetické obvody.

Lecture notes

• Non-uniform notes.

Literatura:

• Ingo Wegener. The complexity of Boolean functions. Verze na webu https://eccc.weizmann.ac.il/static/books/The_Complexity_of_Boolean_Functions/
• 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/