Sylabus
Nedeterministická časová hierarchie a hierarchie pro pravděpodobnostní třídy výpočtů
BPP a polynomiální hierarchie
Time-space trade-off pro SAT
Izolační lema a Todova věta
Pseudonáhodné generátory, Nisanův pseudonáhodný generátor
Interaktivní protokoly - Arthur-Merlin (třída AM, IP=PSPACE)
Interaktivní protokoly s více dokazateli (MIP=NEXP)
Anotace
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.