|
|
| Строка 8: |
Строка 8: |
| | '''[[Класс IP|IP]]'''<tex>[f(n)] = </tex> '''AM'''<tex>[f(n)+ O(1)]</tex> | | '''[[Класс IP|IP]]'''<tex>[f(n)] = </tex> '''AM'''<tex>[f(n)+ O(1)]</tex> |
| | | | |
| − | ==Доказательство==
| + | |
| | Заметим что, '''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>, так как открытые монетки "хуже" закрытых. |
| | | | |
| Строка 22: |
Строка 22: |
| | * <tex>x \notin L \Rightarrow |S|<K</tex>, т.е. если слово не принадлежит языку, то множество вероятностных лент, на которых слово все же будет допущено, должно быть достаточно малым. | | * <tex>x \notin L \Rightarrow |S|<K</tex>, т.е. если слово не принадлежит языку, то множество вероятностных лент, на которых слово все же будет допущено, должно быть достаточно малым. |
| | Число <tex>K</tex> выберем позже. | | Число <tex>K</tex> выберем позже. |
| − |
| |
| − | Итак, есть множество <tex>S \subset 2^{m}</tex>. Построим интерактивный протокол доказательства, такой что:
| |
| − | * если <tex>|S|>2K</tex>, то <tex>V</tex> с высокой вероятностью примет слово;
| |
| − | * если <tex>|S|<K</tex>, то <tex>V</tex> с высокой вероятностью не примет слово.
| |
| − | Выберем <tex>k</tex> так, чтобы <tex>2^{k-2} \le 2K \le 2^{k-1}</tex>.
| |
| − | Возьмем <tex>h \in H_{m,k}</tex> (<tex>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 \Rightarrow P(V(x) = [x \in L]) \le p/2</tex>, то есть в этом случае <tex>V</tex> ошибется с вероятностью не более <tex>\frac{1}{2}p</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>E_s</tex> событие <tex>h(s)=y</tex>. Рассмотрим <tex>y \in 2^m</tex>. <tex>P_{h}(\exists s: h(s)=y) = P_{h}(y \in \bigcup \limits_{s}h(s))= </tex> <tex> P_{h}(\bigcup \limits_{s}E_s) \ge \sum \limits_{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 )</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>, т.е. в этом случае <tex>V</tex> примет слово с вероятностью <tex>\frac{3}{4}p > \frac{1}{2}p</tex>;
| |
| − | * если <tex>|S|>2^{k-1}</tex>, то <tex>V</tex> примет слово с вероятностью, большей, чем <tex>\frac{3}{4}p</tex>, так как с дальнейшим возрастанием мощности <tex>|S|</tex> вероятность того, что <tex>V</tex> примет слово только возрастет.
| |
| − | Теперь, выберем <tex>K</tex>: <tex>K = \frac{1}{3}2^{P(|x|)}</tex>.
| |
| − | Запустим построенный протокол доказательства некоторое константное количество раз для того, чтобы повысить точность, а именно добиться того, чтобы в случае, когда <tex>x \notin L </tex> вероятность того, что <tex>V</tex> ошибется была бы меньше <tex>\frac{1}{3}</tex>.
| |
| − |
| |
| − | Итак, '''IP'''<tex>[f(n)] \subset </tex> '''AM'''<tex>[f(n)+O(1)]</tex>. Теорема доказана.
| |
| | | | |
| | ==Cм. также== | | ==Cм. также== |
| | *[[Теорема Шамира]] | | *[[Теорема Шамира]] |
| | *[[Класс IP]] | | *[[Класс IP]] |
Определение
Протокол Артура-Мерлина - интерактивный протокол доказательства, в котором [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], так как открытые монетки "хуже" закрытых.
Докажем теперь, что IP[math][f(n)] \subset [/math] AM[math][f(n)+O(1)][/math].
Для этого докажем, что любой язык [math]L[/math] из IP[math][f(n)][/math] лежит также в AM[math][f(n)+O(1)][/math].
Пусть языку [math]L[/math] соответствует верификатор [math]V'[/math] для которого, в случае, если [math]x \in L[/math], существует прувер [math]P'[/math] такой, что [math]Pr(V'^{P'}(x) = 1) \ge 2/3[/math].
Теперь мы хотим построить верификатор [math]V[/math] из протокола Артура-Мерлина, использующий вероятностную ленту (доступную пруверу [math]P[/math]) и [math]V'[/math].
Рассмотрим множество вероятностных лент [math]R[/math] и его подмножество [math]S \subset R[/math] - множество лент, на которых осуществляется допуск. В соответствии с протоколом, [math]x \in L \Rightarrow P(V(x) = [x \in L]) \ge \frac{2}{3}[/math], т.е. если слово принадлежит языку, то [math]V[/math] должен вывести YES с достаточно большой вероятностью, а если [math]x \notin L[/math], то [math]P(V(x) = [x \in L]) \lt \frac{1}{3}[/math], т.е. если слово не принадлежит языку, то [math]V[/math] разрешено ошибиться, но с достаточно малой вероятностью. Перефразируем эти условия так:
- [math]x \in L \Rightarrow |S|\gt 2K [/math], т.е. если слово принадлежит языку, то множество вероятностных лент, на которых слово будет допущено должно быть достаточно большим;
- [math]x \notin L \Rightarrow |S|\lt K[/math], т.е. если слово не принадлежит языку, то множество вероятностных лент, на которых слово все же будет допущено, должно быть достаточно малым.
Число [math]K[/math] выберем позже.
Cм. также
