211
правок
Изменения
м
Нет описания правки
Попросим программу ''Prover'' прислать ''Verifier'' 'у значение <tex>A_m()= A(r_1, r_2, ..., r_m)</tex>.
Проверим следующее утверждение: <tex>A_nA_m() = A_{m-1}(r_m)</tex>.
А также сами подставим <tex>r_1, r_2, ..., r_m</tex> в <tex>A(x_1, x_2, ..., x_m)</tex> и проверим правильность присланного значения <tex>A_m()</tex>.
Возвращаем '''true'''.
Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Таким образом, нужно доказать:
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \#SAT \Rightarrow \exists Prover : P(Verifier^{Prover}(x)) \ge 2/3</tex>.
# <tex>\langle \varphi, k \rangle \notin \#SAT \Rightarrow \forall Prover : P(Verifier^{Prover}(x)) \le 1/3</tex>.
Из построения ''Verifier'' 'а видно, что он работает за <tex>O(poly(|input|))</tex>.
}}
