36
правок
Изменения
Нет описания правки
Итак, остается доказать, что написанный ''Verifier'' - корректный ''Verifier'' для языка <tex>\#SAT</tex>. Таким образом, нужно доказать:
# Построенный ''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>.
Доказательство:
