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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
Строка 17: Строка 17:
 
Далее, <tex>h \in H_{m,k}</tex>; <tex>y \in 2^k</tex>. Отправляем запрос <tex>P</tex> на получение <tex>s \in S</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>h(s) = y</tex>, и проверяем, верно ли в действительности, что <tex>s \in S</tex>.
Пусть <tex>p = \frac{2K}{2^k}</tex>.  
+
Пусть <tex>p = \frac{2K}{2^k}</tex>.
*если <tex>|S|<K<\tex>, то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K  \Rightarrow P(\mbox{успех}) \le p/2</tex>.
+
* если <tex>|S| < K </tex> , то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K  P() \le p/2</tex>.

Версия 21:25, 17 мая 2010

Определение

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

Определение

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

Теорема(Голдвассер, Сипсер)

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

План доказательства

Рассмотрим множество вероятностных лент [math]R[/math] и его подмножество [math]S \subset R[/math] - множество лент, на которых осуществляется допуск. Если для некоторого множества [math]S[/math] и числа [math]k[/math] выполняется [math]|S| \gt 2K[/math], то допустим слово.

Доказательство

Итак, есть множество [math]S \subset 2^{m}[/math], и мы хотим доказать, что либо [math]|S| \gt 2K[/math], либо [math]|S| \lt K[/math]. Мы умеем определять, верно ли, что [math]s \in S[/math]. Выберем [math]k[/math] так, чтобы [math]2^{k-2} \le 2K \le 2^{k-1}[/math]. Далее, [math]h \in H_{m,k}[/math]; [math]y \in 2^k[/math]. Отправляем запрос [math]P[/math] на получение [math]s \in S[/math]: [math]h(s) = y[/math], и проверяем, верно ли в действительности, что [math]s \in S[/math]. Пусть [math]p = \frac{2K}{2^k}[/math].

  • если [math]|S| \lt K [/math] , то [math]|h(s)| \lt \frac{p \cdot 2^k}{2} = K P() \le p/2[/math].