Теорема Голдвассера, Сипсера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 10: Строка 10:
  
 
Заметим что, '''AM'''<tex>[f(n)+O(1)] \subset </tex> '''IP'''<tex>[f(n)]</tex> для любой функции <tex>f</tex>, так как открытые монетки "хуже" закрытых.
 
Заметим что, '''AM'''<tex>[f(n)+O(1)] \subset </tex> '''IP'''<tex>[f(n)]</tex> для любой функции <tex>f</tex>, так как открытые монетки "хуже" закрытых.
 +
 +
 +
----
 +
Тут было неправильное доказательство теоремы.
 +
Правильное напишем в следующем году.
 +
То, что было правильно из этого доказательства, перенесено в статью [[Протокол Гольдвассера-Сипсера для оценки размера множества]]

Текущая версия на 19:20, 4 сентября 2022

Определение

Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором [math]P[/math](prover, Merlin) видит вероятностную ленту [math]V[/math](verifier, Arthur)(т.н. public coins)

Определение

AM[math][f(n)][/math] - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов [math]V[/math] к [math]P[/math] не превышает [math]f(n)[/math].

Формулировка теоремы

IP[math][f(n)] = [/math] AM[math][f(n)+ O(1)][/math]


Заметим что, AM[math][f(n)+O(1)] \subset [/math] IP[math][f(n)][/math] для любой функции [math]f[/math], так как открытые монетки "хуже" закрытых.



Тут было неправильное доказательство теоремы. Правильное напишем в следующем году. То, что было правильно из этого доказательства, перенесено в статью Протокол Гольдвассера-Сипсера для оценки размера множества