Laboratory of Mathematical Logic at PDMI

Пятница, 29 апреля, комната 106. Начало в 19:00.

Докладчик: В. И. Трофимов.

Тема: MIP=NEXP.

Abstract

Доклад по статье Babai, Fortnow, Lund.

В докладе будут рассмотрено расширение класса интерактивных протоколов до протоколов с несколькими prover'ами (MIP), и доказано, что класс языков, распознаваемых с помощью таких протоколов в точности совпадает с классом языков, распознаваемых с помощью недетерминированной машины Тьюринга за экспоненциальное время (NEXP).