Изменения

Перейти к: навигация, поиск

Теорема Голдвассера, Сипсера

8 байт добавлено, 20:48, 17 мая 2010
Нет описания правки
==Определение==
<tex>AM[f(n)]</tex> - класс языков, для которых существует интерактивный протокол распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>A</tex> к <tex>M</tex> не превышает <tex>f(n)</tex>.
==Теорема(Голдвассер, Сипсер)==
<tex>IP[f(n)] = AM[f(n)+2]</tex>
Анонимный участник

Навигация