211
правок
Изменения
м
Нет описания правки
Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Таким образом, нужно доказать:
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists Prover : P(Verifier^{Prover}(x\langle \varphi, k \rangle)) \ge 2/3</tex>.# <tex>\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall Prover : P(Verifier^{Prover}(x\langle \varphi, k \rangle)) \le 1/3</tex>.
#Первый факт следует из построения ''Verifier'' 'а.
:Из описанного процесса видно, что с вероятностью большей либо равной <tex>(1 - \frac d p) ^ m</tex> мы дойдем до последнего шага и будем имееть <tex>\tilde{A}_n</tex> вместо <tex>A_n</tex>. Так как на шаге <tex>m</tex> ''Verifier'' вычисляет <tex>A_n</tex> и проверяет значение, то ''Verifier'' вернет ''false''.
:Оценим вероятность возврата ''Verifier'' 'ом ответа '''false'''.
:<tex>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</tex>.
Таким образом, построенный нами ''Verifier'' корректен, а значит лемма доказана.
