City: Saint Petersburg Novosibirsk Kazan Language: Русский English

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

What: Lecture
When: Sunday, 24 March 2019, 13:00–14:30
Where: ПОМИ РАН

Description

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

Video