Изменения

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

Заметим что, очевидно, <tex>AM[f(n)+O(1)] \subset IP[f(n)], \forall f</tex>.

Рассмотрим множество вероятностных лент <tex>R</tex> и его подмножество <tex>S \subset R</tex> - множество лент, на которых осуществляется допуск. В соответствии с протоколом, <tex>x \in L \Rightarrow P(V(x) = [x \in L]) \ge \frac{2}{3}</tex>, т.е. если слово принадлежит языку, то <tex>V</tex> должен вывести YES с достаточно большой вероятностью, а если <tex>x \notin L</tex>, то <tex>P(V(x) = [x \in L]) < \frac{1}{3}</tex>, т.е. если слово не принадлежит языку, то <tex>V</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}</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>. <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>

==Cм. также==

*[[Теорема Шамира]]

*[[Класс IP]]