Изменения

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

Теорема о соотношении coNP и IP

18 байт добавлено, 16:40, 5 июня 2012
м
Нет описания правки
:<tex>\ldots</tex>
:'''Шаг m'''
:Так как на последнем шаге <tex>\mathit{Verifier}</tex> полученным сверяет полученное от <tex>\mathit{Prover}</tex> значение с непосредственно вычисленным, слово будет допущено только в том случае, когда <tex>\mathit{Prover}</tex> смог прислать верное значение, что в свою очередь возможно лишь если на одном из предыдущих шагов был верно угадан корень полинома.
:
:Вычислим вероятность того, что хотя бы раз корень был угадан.

Навигация