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

Доказательства с несколькими пруверами
Interactive proofs

What: Lecture
When: Sunday, 24 March 2019, 11:15–12:45
Where: ПОМИ РАН

Description

Если пруверов несколько, это ограничивает их возможности по вводу верификатора в заблуждение, потому что в ходе диалога можно устраивать очную ставку. За счёт этого класс доказуемых утверждений растёт ещё сильнее. А именно, верна теорема MIP=NEXP. На лекции мы познакомимся с основными идеями, лежащими в основе этого результата.

Video