Изменения
→Доказательство
* <tex>x \notin L \Rightarrow |s|<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>y \in 2^k</tex>. Далее, отправим запрос <tex>P</tex> на получение <tex>s \in S</tex>, такого, что <tex>h(s)=y</tex>, и проверим, верно ли в действительности, что полученный <tex>s \in S</tex>.
