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