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

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

LS 2020/2021

NTIN081 - 2/0 Zk

Čas konání: Čt. 15:40-17:10 (první přednáška 4.3.)
Místo konání: Skrze Zoom https://cesnet.zoom.us/j/4042155019, 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: