211
правок
Изменения
м
Нет описания правки
Докажем теперь, что построенный таким образом ''Verifier'' — корректный. Для этого нужно доказать следующие утверждения:
# Построенный ''Verifier'' - вероятностная машина Тьюринга, совершающая не более полинома от длины входа действий.
# <tex>\langle \varphi, k \rangle \in \mathrm{\#SAT } \Rightarrow \exists Prover : P(Verifier^{Prover}(\langle \varphi, k \rangle)) \ge 2/3</tex>.# <tex>\langle \varphi, k \rangle \notin \mathrm{\#SAT } \Rightarrow \forall Prover : P(Verifier^{Prover}(\langle \varphi, k \rangle)) \le 1/3</tex>.
Докажем эти утверждения.
