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

Вероятностные классы сложности
Сложность вычислений и основы криптографии


Что: Лекция
Когда: Четверг, 21 февраля 2013, 18:30–19:50
Где: ПОМИ РАН

Описание

Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение ошибки в классе BPP, BPP содержится в P/poly, BPP содержится в \( \Sigma_2^P \cap \Pi_2^P \)

Видео