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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Доказательство)
м (rollbackEdits.php mass rollback)
 
(не показано 66 промежуточных версий 3 участников)
Строка 3: Строка 3:
  
 
==Определение==
 
==Определение==
−
<tex>AM[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>V</tex> к <tex>P</tex> не превышает <tex>f(n)</tex>.
+
'''AM'''<tex>[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>V</tex> к <tex>P</tex> не превышает <tex>f(n)</tex>.
  
−
==Теорема(Голдвассер, Сипсер)==
+
==Формулировка теоремы==
−
<tex>IP[f(n)] = AM[f(n)+2]</tex>
+
'''[[Класс IP|IP]]'''<tex>[f(n)] = </tex> '''AM'''<tex>[f(n)+ O(1)]</tex>
  
−
==План доказательства==
 
−
Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. Если для некоторого множества <tex>S</tex> и числа <tex>k</tex> выполняется <tex>|S| > 2K</tex>, то допустим слово.
 
  
−
==Доказательство==
+
Заметим что, '''AM'''<tex>[f(n)+O(1)] \subset </tex> '''IP'''<tex>[f(n)]</tex> для любой функции <tex>f</tex>, так как открытые монетки "хуже" закрытых.
−
Итак, есть множество <tex>S \subset 2^{m}</tex>, и мы хотим доказать, что либо <tex>|S| > 2K</tex>, либо <tex>|S| < K</tex>.
+
 
−
Мы умеем определять, верно ли, что <tex>s \in S</tex>.
+
 
−
Выберем <tex>k</tex> так, чтобы <tex>2^{k-2} \le 2K \le 2^{k-1}</tex>.
+
----
−
Далее, <tex>h \in H_{m,k}</tex>; <tex>y \in 2^k</tex>. Отправляем запрос <tex>P</tex> на получение <tex>s \in S</tex>:
+
Тут было неправильное доказательство теоремы.
−
<tex>h(s) = y</tex>, и проверяем, верно ли в действительности, что <tex>s \in S</tex>.
+
Правильное напишем в следующем году.
−
Пусть <tex>p = \frac{2K}{2^k}</tex>.
+
То, что было правильно из этого доказательства, перенесено в статью [[Протокол Гольдвассера-Сипсера для оценки размера множества]]
−
* если <tex>|S| < K </tex> , то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K  P(\mbox{успех}) \le p/2</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], так как открытые монетки "хуже" закрытых.


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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Голдвассера,_Сипсера&oldid=84928»