Výpočetní složitost a interaktivni protokoly

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

LS 2022/2023

NTIN081 - 2/0 Zk

Čas konání: Út. 14:00-15:30. (První přednáška 21.2.2023.)
Místo konání: S321 (chodba 3. patro), Malá Strana.
Jazyk: česky nebo anglicky dle požadavku studentů (taught in Czech or English depending on students)

Přednáška rozšiřuje základní přednášku o výpočetní složitosti (NTIN063). Seznamuje s hierarchií pro pravděpodobnostní třídy výpočtů, time-space trade-offs pro SAT, Todovou větou, pseudonáhodnými generátory a interaktivními protokoly.

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

Plán přednášky

Literatura: