Теорема Голдвассера, Сипсера — различия между версиями
| Строка 3: | Строка 3: | ||
==Определение== | ==Определение== | ||
| − | <tex>AM[f(n)]<tex> - класс языков, для которых существует интерактивный протокол доказательства Артура-Мерлина, причем количество запросов Артура к Мерлину не превышает <tex>f(n)<tex>. | + | <tex>AM\[f(n)\]<tex> - класс языков, для которых существует интерактивный протокол доказательства Артура-Мерлина, причем количество запросов Артура к Мерлину не превышает <tex>f(n)<tex>. |
==Теорема(Голдвассер, Сипсер)== | ==Теорема(Голдвассер, Сипсер)== | ||
AM = IP | AM = IP | ||
Версия 20:33, 17 мая 2010
Определение
Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором <tex>A<tex>(prover, Arthur) видит вероятностную ленту <tex>M<tex>(verifier, Merlin)(т.н. public coins)
Определение
<tex>AM\[f(n)\]<tex> - класс языков, для которых существует интерактивный протокол доказательства Артура-Мерлина, причем количество запросов Артура к Мерлину не превышает <tex>f(n)<tex>.
Теорема(Голдвассер, Сипсер)
AM = IP
