Изменения

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

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

121 байт добавлено, 16:25, 4 июня 2012
м
Нет описания правки
:Так как на последнем шаге ''Verifier'' сверяет истинное значение с полученным от ''Prover'', слово будет допущено только в том случае, когда ''Prover'' смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
:
:Посчитаем вероятность того, что ''Verifier'' хотя бы раз угадал корень.
:<tex>P(\mathit{Verifier^{Prover}}(\langle \varphi, k \rangle)=1) = 1 - (1 - \frac d p)^m \le 1 - (1 - \frac d {3dm})^m \le \frac 1 3</tex>.

Навигация