Теорема Голдвассера, Сипсера — различия между версиями
(→Доказательство) |
(→Доказательство) |
||
Строка 20: | Строка 20: | ||
Пусть <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>P_{h,y}(\exists s: h(s)=y) \ge \frac{3}{4} \cdot \frac{|s|}{2K}</tex> . Рассмотрим <tex>y \in 2^m</tex>. <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 )</math> | + | * если <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>E_s</tex> событие <tex>h(s)=y</tex>. Рассмотрим <tex>y \in 2^m</tex>. <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 )</math> |
Заметим, что <tex>|s|\frac{1}{2^k} > p</tex>, а <tex>\frac{|s|}{2^{k+1}} < \frac{1}{4}</tex>. Следовательно, <tex>P_{h}(\exists s: h(s)=y) > \frac{3}{4}p</tex> | Заметим, что <tex>|s|\frac{1}{2^k} > p</tex>, а <tex>\frac{|s|}{2^{k+1}} < \frac{1}{4}</tex>. Следовательно, <tex>P_{h}(\exists s: h(s)=y) > \frac{3}{4}p</tex> |
Версия 13:27, 18 мая 2010
Определение
Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором (prover, Merlin) видит вероятностную ленту (verifier, Arthur)(т.н. public coins)
Определение
- класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов к не превышает .
Формулировка теоремы
Доказательство
Рассмотрим множество вероятностных лент
и его подмножество - множество лент, на которых осуществляется допуск. В соответствии с протоколом, , то есть если слово принадлежит языку, то должен вывести с достаточно большой вероятностью, а если , то , то есть если слово не принадлежит языку, то разрешено ошибиться, но с достаточно малой вероятностью. Перефразируем эти условия так:- , т.е. если слово принадлежит языку, то множество вероятностных лент, на которых слово будет допущено должно быть достаточно большим;
- , т.е. если слово не принадлежит языку, то множество вероятностных лент, на которых слово все же будет допущено, должно быть достаточно малым.
Итак, есть множество
, и мы хотим доказать, что:- если , то с высокой вероятностью примет слово;
- если , то с высокой вероятностью не примет слово.
Выберем семейство универсальных попарно независимых хеш-функций, и . Далее, отправим запрос на получение , такого, что , и проверим, верно ли в действительности, что полученный . Пусть .
так, чтобы . Возьмем -- если , то успех .
- если , и , то поступим следующим образом. Мы хотим, чтобы выполнялось: . Обозначим как событие . Рассмотрим .
Заметим, что
, а . Следовательно,