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