|
Для доказательства леммы построим программы [math]\mathit{Verifier}[/math] и [math]\mathit{Prover}[/math] из определения класса [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 \mathrm{\#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].
Приступим к описанию [math]\mathit{Verifier}[/math]'а.
Шаг 0
Если [math]d=0[/math] или [math]m=0[/math], то [math]\mathit{Verifier}[/math] может проверить указанное выше условие сам и вернуть соответствующий результат.
Иначе запросим у [math]\mathit{Prover}[/math]'а такое простое число [math]p[/math], что [math]3dm \le p \le 6dm[/math] (такое [math]p[/math] существует в силу постулата Бертрана).
Проверим [math]p[/math] на простоту и на принадлежность заданному промежутку. Как мы знаем, [math]\mathrm{Primes} \in \mathrm{P}[/math], следовательно на эти операции у [math]\mathit{Verifier}[/math]'а уйдёт полиномиальное от размера входа время.
Далее будем проводить все вычисления модулю [math]p[/math].
Попросим [math]\mathit{Prover}[/math] 'а прислать [math]\mathit{Verifier}[/math]'у формулу [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] будет полином от длины входа [math]\mathit{Verifier}[/math] 'а, так как [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] (*) (здесь и далее под словом «проверим» будем подразумевать следующее: если утверждение верно, [math]\mathit{Verifier}[/math] продолжает свою работу, иначе он прекращает свою работу и возвращет false).
Шаг i
Пусть [math]r_i = random(0..p-1)[/math]. Отправим [math]r_i[/math] программе [math]\mathit{Prover}[/math].
Попросим [math]\mathit{Prover}[/math] 'а прислать [math]\mathit{Verifier}[/math]'у формулу [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(0..p-1)[/math]. Отправим [math]r_m[/math] программе [math]\mathit{Prover}[/math].
Попросим программу [math]\mathit{Prover}[/math] прислать [math]\mathit{Verifier}[/math]'у значение [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.
Докажем теперь, что построенный таким образом [math]\mathit{Verifier}[/math] — корректный. Для этого нужно доказать следующие утверждения:
- Построенный [math]\mathit{Verifier}[/math] - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
- [math]\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3[/math].
- [math]\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3[/math].
Докажем эти утверждения.
- Первый факт следует из построения [math]\mathit{Verifier}[/math] 'а.
- По лемме (2), если [math]\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k[/math], то условия (*) выполнятются, следовательно существует такой [math]\mathit{Prover}[/math], что [math]P(\mathit{Verifier^{Prover}}(\langle\phi,k\rangle)) = 1[/math], для любой пары [math]\langle\phi,k\rangle \in \mathrm{\#SAT}[/math].
- Пусть количество наборов, удовлетворяющих [math]\phi[/math], не равно [math]k[/math]. Для того, что бы [math]\mathit{Verifier}[/math] вернул true, [math]\mathit{Prover}[/math] 'у необходимо посылать такие [math]A_i[/math], чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
- Шаг 0
- Так как количество наборов, удовлетворяющих [math]\phi[/math], не равно [math]k[/math], то [math]\mathit{Prover}[/math] не может послать правильное [math]A_0[/math], поскольку в этом случае не выполнится условие [math]A_0(0) + A_0(1) = k[/math]. Поэтому он посылает не [math]A_0[/math], а некое [math]\tilde{A}_0[/math].
- [math]\ldots[/math]
- Шаг i
- Заметим, что если на каком-то шаге [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], то начиная со следующего шага [math]\mathit{Prover}[/math] может посылать правильные [math]A_j[/math] и в итоге [math]\mathit{Verifier}[/math] вернёт true.
- Для некоторого случайно выбранного [math]r_i[/math] вероятность того, что [math]A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)[/math], то есть [math]r_i[/math] — корень полинома [math](A_{i-1} - \tilde{A}_{i-1})(r_i)[/math], имеющего степень не больше [math]d[/math], не превосходит [math]\frac{d}{p}[/math].
- [math]\ldots[/math]
- Шаг m
- Так как на последнем шаге [math]\mathit{Verifier}[/math] сверяет полученное от [math]\mathit{Prover}[/math]'а значение с непосредственно вычисленным, слово будет допущено только в том случае, когда [math]\mathit{Prover}[/math] смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
- Вычислим вероятность того, что хотя бы раз корень был угадан.
- [math]P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3[/math].
- В последнем переходе мы воспользовались формулой Тейлора для логарифма и экспоненты, а также тем, что [math]m\gt 0[/math].
Таким образом, построенный нами [math]\mathit{Verifier}[/math] корректен, а значит лемма доказана. |
