PředmětyPředměty(verze: 837)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Výpočetní složitost - NTIN082
Anglický název: Computational Complexity
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2019
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: prof. Mgr. Michal Koucký, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: T_KTI (26.04.2016)
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.
Cíl předmětu
Poslední úprava: 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ů.

Literatura -
Poslední úprava: T_KTI (26.04.2016)

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.

Sylabus -
Poslední úprava: T_KTI (26.04.2016)

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 AC0 - důkaz Razborova a Smolenského

Aproximace MAJ je v AC0

ACC0 vs CC0

Redukce hloubky obvodu

Williams: NEXP není v ACC0

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

 
Univerzita Karlova | Informační systém UK