Изменения

Перейти к: навигация, поиск

Лемма о соотношении coNP и IP

47 байт добавлено, 01:17, 4 июня 2012
м
Нет описания правки
# <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'' 'а.

Навигация