Изменения

* если <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>K</tex>: <tex>K = \frac{1}{3}2^{P(|x|)}</tex>.

Запустим построенный протокол доказательства некоторое константное количество раз для того, чтобы повысить точность, а именно добиться того, чтобы было: <tex>x \notin L \Rightarrow P(V(x) = [x \in L]) < \frac{1}{3}</tex>.