Изменения

# <tex>\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge 2/3</tex>.# <tex>\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall \mathit{Prover} : P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \le 1/3</tex>.

: Допустим до шага <tex>P(A_{m-1}(r_m) \ne \tilde{A}_{m-1}(r_m)) \ge 1 - \frac d p</tex>. Значит с такой вероятностью ''Verifier'' получит мы ни разу не угадали корень <tex>\tilde{A}_m</tex> вместо <tex>A_m</tex>. Но так как на шаге <tex>mr_i</tex> , то есть ''Prover'' каждый обманывал ''Verifier'' вычисляет <tex>A_m</tex> и сравнивает его . Так как на последнем шаге сверяем истинное значение с полученным от присланным ''Prover'' 'аом, то в этом случае ''Verifier'' вернет не допустит слово. Значит ''falseVerifier''могу допустить слово только если на каком-то шаге был угадан корень.

:Из описанного процесса видно, что с вероятностью большей либо равной <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(!\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) \ge le \frac d p \sum \limits_{i=0}^{m-1} (1 - \frac d p) ^ m \ge i = 1 - (1 - \frac d {3dm}p)^m = \le 1 - (1 - \frac 1 d {3m3dm})^m = 1 - \frac 1 3 + \frac{m(m - 1)}{2 (3m)^2} - \frac{m(m-1)(m-2)}{6 (3m})^3} + m \ldots \ge le \frac 2 1 3</tex>.