Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 9. Вероятностные классы сложности.
Теория сложности вычислений

Что: Лекция
Когда: Вторник, 09 ноября 2021, 18:30–19:50
Где: Конференция в zoom, Онлайн
Слайды: computationalcomplexity_lecture_091121.pdf

Описание

Вероятностные машины Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля. Тестирование равенства полиномов. Проверка на равенство однопроходных ветвящихся программ. Теорема Адлемана. Теорема Сипсера-Гача.

Видео