Изменения

Теорема Голдвассера, Сипсера

82 байта убрано, 11:22, 18 мая 2010

→‎Доказательство

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

Итак, есть множество <tex>S \subset 2^{m}</tex>, и мы хотим доказать, что либо <tex>|S| > 2K</tex>, либо <tex>|S| < K</tex>.

~~Мы умеем определять, верно ли, что <tex>s \in S</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>:

Анонимный участник