Изменения
Нет описания правки
Докажем теперь, что построенный таким образом <tex>\mathit{Verifier}</tex> — корректный. Для этого нужно доказать следующие утверждения:
# Построенный <tex>\mathit{Verifier}</tex> - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT} \Rightarrow \exists \mathit{Prover} : P(\Pr[\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) ] \ge 2/3</tex>.# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT} \Rightarrow \forall \mathit{Prover} : P(\Pr[\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) ] \le 1/3</tex>.
Докажем эти утверждения.
#Первый факт следует из построения <tex>\mathit{Verifier}</tex> 'а.
#По [[Арифметизация булевых формул с кванторами | лемме (2)]], если <tex>\sum\limits_{x_1 = 0}^1 \ldots \sum\limits_{x_m = 0}^1 A_\phi(x_1, \ldots, x_m)=k</tex>, то условия (*) выполнятются, следовательно существует такой <tex>\mathit{Prover}</tex>, что <tex>P(\Pr[\mathit{Verifier^{Prover}}(\langle\phi,k\rangle)) = 1] = 1</tex>, для любой пары <tex>\langle\phi,k\rangle \in \mathrm{\#SAT}</tex>.
#Пусть количество наборов, удовлетворяющих <tex>\phi</tex>, не равно <tex>k</tex>. Для того, что бы <tex>\mathit{Verifier}</tex> вернул '''true''', <tex>\mathit{Prover}</tex> 'у необходимо посылать такие <tex>A_i</tex>, чтобы выполнялись все проверяемые условия. Посмотрим на то, что он может послать:
:'''Шаг 0'''
:
:Вычислим вероятность того, что хотя бы раз корень был угадан.
:<tex>P(\Pr[\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</tex>.
:В последнем переходе мы воспользовались [http://ru.wikipedia.org/wiki/Ряд_Тейлора формулой Тейлора] для логарифма и экспоненты, а также тем, что <tex>m>0</tex>.
