1632
правки
Изменения
м
==Доказательство==
Заметим что, очевидно, <tex>AM[f(n)] \subset IP[f(n)], \forall f</tex>.
Докажем теперь, что <tex>IP \subset AM</tex>
Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. В соответствии с протоколомЗаметим что, '''AM'''<tex>x \in L \Rightarrow P[f(Vn)+O(x1) = [x \in L]) \ge \frac{2}{3}subset </tex>, т.е. если слово принадлежит языку, то '''IP'''<tex>V</tex> должен вывести <tex>YES</tex> с достаточно большой вероятностью, а если <tex>x \notin L</tex>, то <tex>P(V[f(xn) = [x \in L]) < \frac{1}{3}</tex>, т.е. если слово не принадлежит языку, то для любой функции <tex>Vf</tex> разрешено ошибиться, но с достаточно малой вероятностью. Перефразируем эти условия так: * <tex>x \in L \Rightarrow |s|>2K </tex>, т.е. если слово принадлежит языку, то множество вероятностных лент, на которых слово будет допущено должно быть достаточно большим;* <tex>x \notin L \Rightarrow |s|<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{p}{2}</tex>;
* если <tex>|S|>2K</tex>, и <tex>|S|<2^{k-1}</tex>, то поступим следующим образом. Мы хотим, чтобы выполнялось: <math>\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))=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>V</tex> примет слово с вероятностью <tex>\frac{3}{4}p > \frac{p}{2}</tex>.
Теперь, выберем <tex>K</tex>: <tex>K = \frac{1}{3}2^{P(|x|)}</tex>. Итак, <tex>IP \subset AM</tex>. Теорема доказана.
==Cм----Тут было неправильное доказательство теоремы. также==*[[Теорема Шамира]]Правильное напишем в следующем году.*То, что было правильно из этого доказательства, перенесено в статью [[Класс IPПротокол Гольдвассера-Сипсера для оценки размера множества]]
rollbackEdits.php mass rollback
==Определение==
'''AM'''<tex>AM[f(n)]</tex> - класс языков, распознаваемых с помощью интерактивного протокола доказательства Артура-Мерлина, причем количество запросов <tex>V</tex> к <tex>P</tex> не превышает <tex>f(n)</tex>.
==Формулировка теоремы==
'''[[Класс IP|IP]]'''<tex>IP[f(n)] = </tex> '''AM'''<tex>[f(n)+ O(1)]</tex>
