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