|
Известия Российской академии наук. Серия математическая, 1993, том 57, выпуск 3, страницы 152–178
(Mi im871)
|
|
|
|
О возможности проведения любого активного доказательства за ограниченное число раундов
О. В. Вербицкий
Аннотация:
В 1990 г. Бабаи, Фортнов и Ланд построили мультиинтерактивную систему доказательств для некоторого $\operatorname{NEXP}$-полного множества. Тем самым было доказано совпадение сложностных классов $\operatorname{MIP}$ и $\operatorname{NEXP}$. В настоящей работе для произвольного заданного $\operatorname{NEXP}$-множества строится мультиинтерактивный протокол $\langle V,\ P_1,\ P_2\rangle$ c допустимой вероятностью ошибки $1/3$ и количеством раундов, ограниченным некоторой универсальной константой $c$, т.е. доказывается совпадение классов $\operatorname{MIP}$ и $\operatorname{IP(2,c)}$ для некоторой константы $c$.
Поступило в редакцию: 12.12.1991
Образец цитирования:
О. В. Вербицкий, “О возможности проведения любого активного доказательства за ограниченное число раундов”, Изв. РАН. Сер. матем., 57:3 (1993), 152–178; Russian Acad. Sci. Izv. Math., 42:3 (1994), 561–586
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/im871 https://www.mathnet.ru/rus/im/v57/i3/p152
|
Статистика просмотров: |
Страница аннотации: | 230 | PDF русской версии: | 78 | PDF английской версии: | 4 | Список литературы: | 31 | Первая страница: | 2 |
|