Изменения

# Завершите доказательство корректности протокола большого множества, который позволяет различать случаи $|S| = a$ и $|S| = a/2$.

# Протокол большого множества можно модифицировать, чтобы если множество большое, Prover мог добиться, чтобы Verifier принимал с вероятностью 1. Из каких компонент сложить решение: пусть $S \subset \mathbb{B}^n$, $|S| = a$ или $|S| = a/c$, где $c$ - параметр, который выберем позже, $H$ - универсальное семейство попарно независимых хеш-функций из $\mathbb{B}^n в $\mathbb{B}^k$. Можно выбрать такое $c$ и такое $t$, полиномиальное от $n$, что если $|S| = a$, то существуют $t$ хеш-функций $h_1, \ldots, h_t$, что $\cup h_i(S) = \mathbb{B}^k$, а если $|S| = a/c$, то для любых $t$ хеш-функций $|\cup h_i(S)| < 2^{k-1}$. При этом $c$ можно менять, рассматривая вместо $S$ множество $S^z$ для целого $z$. Совет: вспомнить доказательство теоремы Лаутемана.