Теорема Голдвассера, Сипсера — различия между версиями
(Новая страница: «==Теорема(Голдвассер, Сипсер)== AM = IP») |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 84 промежуточные версии 3 участников) | |||
| Строка 1: | Строка 1: | ||
| − | == | + | ==Определение== |
| − | AM = IP | + | '''Протокол Артура-Мерлина''' - [[Класс IP|интерактивный протокол доказательства]], в котором <tex>P</tex>(prover, Merlin) видит вероятностную ленту <tex>V</tex>(verifier, Arthur)(''т.н. public coins'') |
| + | |||
| + | ==Определение== | ||
| + | '''AM'''<tex>[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>V</tex> к <tex>P</tex> не превышает <tex>f(n)</tex>. | ||
| + | |||
| + | ==Формулировка теоремы== | ||
| + | '''[[Класс IP|IP]]'''<tex>[f(n)] = </tex> '''AM'''<tex>[f(n)+ O(1)]</tex> | ||
| + | |||
| + | |||
| + | Заметим что, '''AM'''<tex>[f(n)+O(1)] \subset </tex> '''IP'''<tex>[f(n)]</tex> для любой функции <tex>f</tex>, так как открытые монетки "хуже" закрытых. | ||
| + | |||
| + | |||
| + | ---- | ||
| + | Тут было неправильное доказательство теоремы. | ||
| + | Правильное напишем в следующем году. | ||
| + | То, что было правильно из этого доказательства, перенесено в статью [[Протокол Гольдвассера-Сипсера для оценки размера множества]] | ||
Текущая версия на 19:20, 4 сентября 2022
Определение
Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором (prover, Merlin) видит вероятностную ленту (verifier, Arthur)(т.н. public coins)
Определение
AM - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов к не превышает .
Формулировка теоремы
IP AM
Заметим что, AM IP для любой функции , так как открытые монетки "хуже" закрытых.
Тут было неправильное доказательство теоремы. Правильное напишем в следующем году. То, что было правильно из этого доказательства, перенесено в статью Протокол Гольдвассера-Сипсера для оценки размера множества
