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

Рациональные интерактивные доказательства
Интерактивные доказательства


Что: Лекция
Когда: Воскресенье, 24 марта 2019, 13:00–14:30
Где: ПОМИ

Описание

Это сравнительно новая концепция, возникшая на стыке сложности вычислений и теории игр. Пусть прувер теперь не честный и не жульничающий, а меркантильный. Верификатор по итогам диалога выплачивает некоторую полиномиально вычислимую сумму, а прувер, максимизируя эту сумму, выявляет правильный ответ. Оказывается, класс доказуемых утверждений не изменится, но может существенно сократиться необходимое число раундов общения.