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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 17: Строка 17:
 
Пусть <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(</tex>успех<tex>) \le p/2</tex>.
 
* если <tex>|S|<K</tex> , то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K \Rightarrow P(</tex>успех<tex>) \le p/2</tex>.
* если <tex>|S|>2K</tex>, и <tex>|S|<2^{k-1}</tex>, то поступим следующим образом. Мы хотим, чтобы выполнялось:  
+
* если <tex>|S|>2K</tex>, и <tex>|S|<2^{k-1}</tex>, то поступим следующим образом. Мы хотим, чтобы выполнялось: <tex>P_{h,y}(\exists s: h(s)=y) \ge \frac{3}{4} \cdot \frac{|s|}{2K}</tex> Рассмотрим <tex>y \in 2^m</tex>. <tex>P_{h}(\exists s: h(s)=y) = P_{h}(y \in \bigcup \limits_{s}h(s))=P_{h}(\bigcup \limits_{s}E_s) \ge \sum_{j}P(E_s)-\sum \limits_{s_1 \ne s_2}P(E_{s_1} \bigcap E_{s_2})= \frac{|s|}{2^k}-\frac{1}{2}|s|^{2}\frac{1}{2^{2k}}=|s|\frac{1}{2^k}\left ( 1 - \frac{|s|}{2^{k+1}} \right ) > \frac{3}{4}p</tex>
<tex>P_{h,y}(\exists s: h(s)=y) \ge \frac{3}{4} \cdot \frac{|s|}{2K}</tex>.
 
Рассмотрим <tex>y \in 2^m</tex>. <tex>P_{h}(\exists s: h(s)=y) = P_{h}(y \in \bigcup \limits_{s}h(s))=P_{h}(\bigcup \limits_{s}E_s) \ge \sum_{j}P(E_s)-\sum \limits_{s_1 \ne s_2}P(E_{s_1} \bigcap E_{s_2})= \frac{|s|}{2^k}-\frac{1}{2}|s|^{2}\frac{1}{2^{2k}}=|s|\frac{1}{2^k}\left ( 1 - \frac{|s|}{2^{k+1}} \right ) > \frac{3}{4}p</tex>
 

Версия 11:32, 18 мая 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]k[/math] так, чтобы [math]2^{k-2} \le 2K \le 2^{k-1}[/math]. Возьмем [math]h \in H_{m,k}[/math] ([math]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 \Rightarrow P([/math]успех[math]) \le p/2[/math].
  • если [math]|S|\gt 2K[/math], и [math]|S|\lt 2^{k-1}[/math], то поступим следующим образом. Мы хотим, чтобы выполнялось: [math]P_{h,y}(\exists s: h(s)=y) \ge \frac{3}{4} \cdot \frac{|s|}{2K}[/math] Рассмотрим [math]y \in 2^m[/math]. [math]P_{h}(\exists s: h(s)=y) = P_{h}(y \in \bigcup \limits_{s}h(s))=P_{h}(\bigcup \limits_{s}E_s) \ge \sum_{j}P(E_s)-\sum \limits_{s_1 \ne s_2}P(E_{s_1} \bigcap E_{s_2})= \frac{|s|}{2^k}-\frac{1}{2}|s|^{2}\frac{1}{2^{2k}}=|s|\frac{1}{2^k}\left ( 1 - \frac{|s|}{2^{k+1}} \right ) \gt \frac{3}{4}p[/math]