|
Для доказательства леммы построим программы Verifier и Prover из определения класса [math]\mathrm{IP}[/math].
Сперва арифметизуем формулу [math]\phi[/math]. Пусть полученный полином [math]A(x_1, x_2, ..., x_m)[/math] имеет степень [math]d[/math].
По лемме (1) вместо условия [math]\langle \phi, k \rangle \in \#SAT[/math], можно проверять условие [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k[/math].
Приступим к описанию Verifier'а.
Шаг 0
Запросим у Prover'а такое простое число [math]p[/math], что [math]max(2^m+1, 3dm) \le p \le 2 \cdot max(2^m+1, 3dm)[/math].
Проверим [math]p[/math] на простоту и на принадлежность заданному промежутку. Как мы знаем, [math]Primes \in \mathrm{P}[/math], следовательно на эти операции у Verifier'а уйдёт полиномиальное от размера входа время.
Далее будем проводить все вычисления модулю [math]p[/math].
Попросим Prover 'а прислать Verifier 'у формулу [math]A_0(x_1)= \sum\limits_{x_2 = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(x_1, x_2, ..., x_m)[/math].
Заметим, что размер формулы [math]A_0(x_1)[/math] будет полином от длины входа Verifier 'а, так как [math]A_0(x_1)[/math] полином от одной переменной степени не выше, чем [math]d[/math], а значит его можно представить в виде [math]A_0(x) = \sum\limits_{i = 0}^{d} C_i \cdot x ^ i[/math].
Проверим следующее утверждение: [math]A_0(0) + A_0(1) = k[/math] (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, Verifier продолжает свою работу, иначе он прекращает свою работу и возвращет false).
Шаг i
Пусть [math]r_i = random(p)[/math]. Отправим [math]r_i[/math] программе Prover.
Попросим Prover 'а прислать Verifier 'у формулу [math]A_i(x_{i+1}) = \sum\limits_{x_{i+2} = 0}^{1}\ldots\sum\limits_{x_m = 0}^{1} A(r_1,\ldots, r_i, x_{i+1}, ..., x_m)[/math].
Проверим следующее утверждение: [math]A_i(0) + A_i(1) = A_{i-1}(r_i)[/math].
Шаг m
Пусть [math]r_m = random(p)[/math]. Отправим [math]r_m[/math] программе Prover.
Попросим программу Prover прислать Verifier 'у значение [math]A_m()= A(r_1, r_2, ..., r_m)[/math].
Проверим следующее утверждение: [math]A_m() = A_{m-1}(r_m)[/math].
А также сами подставим [math]r_1, r_2, ..., r_m[/math] в [math]A(x_1, x_2, ..., x_m)[/math] и проверим правильность присланного значения [math]A_m()[/math].
Возвращаем true.
Докажем теперь, что построенный таким образом Verifier — корректный. Таким образом, нужно доказать:
- Построенный Verifier - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
- [math]\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists Prover : P(Verifier^{Prover}(\langle \varphi, k \rangle)) \ge 2/3[/math].
- [math]\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall Prover : P(Verifier^{Prover}(\langle \varphi, k \rangle)) \le 1/3[/math].
- Первый факт следует из построения Verifier 'а.
- По лемме (2), если [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k[/math], то условия (*) выполнятются, следовательно существует такой Prover, что [math]P(Verifier^{Prover}(\langle\phi,k\rangle)) = 1[/math], для любой пары [math]\langle\phi,k\rangle \in \#SAT[/math].
- Пусть количество наборов, удовлетворяющих [math]\phi[/math], не равно [math]k[/math]. Для того, что бы Verifier вернул true, Prover 'у необходимо посылать такие [math]A_i[/math], чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
- Шаг 0
- Так как количество наборов, удовлетворяющих [math]\phi[/math], не равно [math]k[/math], то Prover не может послать правильное [math]A_0[/math] – не выполнится условие [math]A_0(0) + A_0(1) = k[/math]. Поэтому он посылает не [math]A_0[/math], а некое [math]\tilde{A}_0[/math].
- Шаг 1
- По лемме Шварца-Зиппеля [math]P(A_0(r_1) = \tilde{A}_0(r_1)) \le \frac d p[/math] для некоторого случайно выбранного [math]r_1[/math]. Тогда [math]P(A_0(r_1) \ne \tilde{A}_0(r_1)) \ge 1 - \frac d p[/math], при этом должно выполняться равенство [math]A_1(0) + A_1(1) = A_0(r_1)[/math]. Значит с вероятностью не меньше, чем [math]1 - \frac d p[/math], Prover отправит Verifier 'у [math]\tilde{A}_1[/math] вместо [math]A_1[/math].
- [math]\ldots[/math]
- Шаг m
- [math]P(A_{m-1}(r_m) \ne \tilde{A}_{m-1}(r_m)) \ge 1 - \frac d p[/math]. Значит с такой вероятностью Verifier получит [math]\tilde{A}_m[/math] вместо [math]A_m[/math]. Но так как на шаге [math]m[/math] Verifier вычисляет [math]A_m[/math] и сравнивает его с полученным от Prover 'а, то в этом случае Verifier вернет false.
- Заметим, что если на каком-то шаге [math]P(A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i))[/math], то начиная со следующего шага Prover может посылать истинные значения [math]A_i[/math] и в итоге Verifier вернёт true.
- Из описанного процесса видно, что с вероятностью большей либо равной [math](1 - \frac d p) ^ m[/math] мы дойдем до последнего шага и будем имееть [math]\tilde{A}_n[/math] вместо [math]A_n[/math]. Так как на шаге [math]m[/math] Verifier вычисляет [math]A_n[/math] и проверяет значение, то Verifier вернет false.
- Оценим вероятность возврата Verifier 'ом ответа false.
- [math]P(!Verifier^{Prover}(\langle \varphi, k \rangle)) \ge (1 - \frac d p) ^ m \ge (1 - \frac d {3dm})^m = (1 - \frac 1 {3m})^m = 1 - \frac 1 3 + \frac{m(m - 1)}{2 (3m)^2} - \frac{m(m-1)(m-2)}{6 (3m)^3} + \ldots \ge \frac 2 3[/math].
Таким образом, построенный нами Verifier корректен, а значит лемма доказана. |
