Изменения
→Доказательство
Далее, <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>.
Пусть <tex>p = \frac{2K}{2^k}</tex>.
*если <tex>|S|<K<\tex>, то <tex>|h(s)| < \frac{p \cdot 2^k}{2} = K \Rightarrow P(\mbox{успех}) \le p/2</tex>.
