40
правок
Изменения
Нет описания правки
==Класс IP==
{{Определение
|definition =
Интерактивным протоколом называется абстрактная машина, моделирующая вычисления как обмен сообщениями между двумя программами (<tex>Prover</tex> и <tex>Verifier</tex>), такими, что
# <tex>Prover</tex> убеждает <tex>Verifier</tex> в том, что слово <tex>x</tex> принадлежит языку
# <tex>Prover</tex> не ограничен в вычислительной мощности
# <tex>Verifier</tex> — вероятностная машина Тьюринга
# <tex>Verifier</tex> ограничен полиномиальным временем работы
}}
Далее <tex>Prover</tex> обозначается <tex>P</tex>, а <tex>Verifier</tex> — <tex>V</tex>.
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex> (см. рис. 1).
{{Определение
|definition =
<tex>IP[f] = \{L|\exists \langle V, P \rangle : </tex> <br/>
# <tex> 1) \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex><br/># <tex> 2) \forall x \notin L \Rightarrow P(V(x) = 1) \le \frac{1}{3} </tex><br/><tex> 3) </tex> Число # число раундов интерактивного протокола <tex> O(f(n)), n = |x| </tex><br/>
}}
