210
правок
Изменения
Нет описания правки
'''Шаг i'''
Пусть <tex>r_i = \mathrm{random } \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_i</tex> программе <tex>P</tex>.
Попросим <tex>P</tex> прислать <tex>V</tex> формулу <tex>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}, \ldots, x_m)</tex>.
'''Шаг m'''
Пусть <tex>r_m = \mathrm{random } \lbrace0, \ldots, p-1 \rbrace</tex>. Отправим <tex>r_m</tex> программе <tex>P</tex>.
Попросим программу <tex>P</tex> прислать <tex>V</tex> значение <tex>A_m()= A(r_1, r_2, \ldots, r_m)</tex>.
Докажем эти утверждения.
#Первый факт следует из построения <tex>\mathit{Verifier}V</tex> 'а.#По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\varphi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполнятютсявыполняются, а значит, по построению протокола, следовательно существует такой <tex>\mathit{Prover}P</tex>, что <tex>\Pr[\mathitmathbb{Verifier^P}(V_{Prover}P}(\langle\varphi,k\rangle) = 1] ) = 1</tex>, для любой пары <tex>\langle\varphi,k\rangle \in \mathrm{\#SAT}</tex>.#Пусть количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>. Для того, что бы чтобы <tex>\mathit{Verifier}V</tex> вернул '''true''', <tex>\mathit{Prover}P</tex> 'у необходимо должен посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
:'''Шаг 0'''
:Так как количество наборов, удовлетворяющих <tex>\varphi</tex>, не равно <tex>k</tex>, то <tex>\mathit{Prover}</tex> не может послать правильное <tex>A_0</tex>, поскольку в этом случае не выполнится условие <tex>A_0(0) + A_0(1) = k</tex>. Поэтому он посылает не <tex>A_0</tex>, а некое <tex>\tilde{A}_0</tex>.
:<tex>\ldots</tex>
:'''Шаг i'''
:Заметим, что если на каком-то шаге <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то начиная со следующего шага <tex>\mathit{Prover}P</tex> может посылать правильные <tex>A_j</tex> и в итоге <tex>\mathit{Verifier}V</tex> вернёт '''true'''.:Для некоторого случайно выбранного <tex>r_i</tex> вероятность того, что <tex>A_{i-1}(r_i) = \tilde{A}_{i-1}(r_i)</tex>, то есть не превосходит <tex>\dfrac{d}{p}</tex>, так как <tex>r_i</tex> — корень полинома <tex>(A_{i-1} - \tilde{A}_{i-1})(r_i)</tex>, имеющего степень не больше <tex>d</tex>, не превосходит а, по основной теореме алгебры, полином имеет ровно <tex> d </tex> корней, и <tex>r_i \frac{d}{in \lbrace 0, \ldots, p}-1 \rbrace</tex>.
:<tex>\ldots</tex>
:'''Шаг m'''
:Так как на последнем шаге <tex>\mathit{Verifier}V</tex> сверяет полученное от <tex>\mathit{Prover}P</tex>'а значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>\mathit{Prover}P</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
:
:Вычислим вероятность того, что хотя бы раз корень был угадан.
:<tex>\Pr[\mathitmathbb{Verifier^P}(V_{Prover}P}(\langle \varphi, k \rangle)=1] ) = 1 - \left(1 - \frac dfrac{d }{p} \right)^m \le leqslant 1 - \left(1 - \frac dfrac{d }{3dm}\right)^m = 1 - \le left(1 - \frac dfrac{1 3}{3m}\right)^m </tex>.:В последнем переходе мы воспользовались [http:Заметим, что функция <tex> y(m) = 1 - \left( 1 - \dfrac{1}{3m} \right)^{m}</tex> убывает при <tex> m \geqslant \dfrac{1}{3} </rutex>.wikipedia.orgА так как <tex> m \geqslant 1 </wikitex> и <tex> y(1) = \dfrac{1}{3} </Ряд_Тейлора формулой Тейлора] для логарифма и экспонентыtex>, а также темв итоге получаем, что <tex>m>0\mathbb{P}(V_{P}(\langle \varphi, k \rangle)=1) \leqslant \dfrac{1}{3} </tex>.
Таким образом, построенный нами <tex>\mathit{Verifier}</tex> интерактивный протокол корректен, а значит лемма доказана.
}}
