40
правок
Изменения
Нет описания правки
{{Определение
|definition =
<b>Интерактивным протоколом </b>, разрешающим язык <tex>L</tex>, называется абстрактная машина(см. рис. 1), моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что# <tex>ProverP</tex> убеждает <tex>VerifierV</tex> в том, что слово <tex>x</tex> принадлежит языку;# <tex>ProverP</tex> не ограничен в вычислительной мощности;# <tex>VerifierV</tex> — вероятностная машина Тьюринга;# <tex>VerifierV</tex> ограничен полиномиальным временем работы.
}}
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex> (см. рис. 1):# <b> public coins </b> — <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>;# <b> private coins </b> — <tex>P</tex> <b>не</b> может видеть вероятностную ленту <tex>V</tex>.
{{Определение
# число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex><br/>
}}
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow P(V(x) = 1) = 1 </tex>, то говорят, что он обладает свойством <b> completeness </b> (его можно достичь).
}}
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow P(V(x) = 1) = 0 </tex>, то говорят, что он обладает свойством <b> soundness </b> (его нельзя достичь достичь).
}}
{{Теорема
