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