Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
==Класс IPОпределения ==
{{Определение
|definition =
<b>Интерактивным протоколом</b>, разрешающим язык <tex>L</tex>, называется абстрактная машина (см. рис. 1рисунок), моделирующая вычисления как обмен сообщениями между двумя программами (Prover и Verifier, далее <tex>P</tex> и <tex>V</tex> соответственно), такими, что
# <tex>P</tex> заинтересован в том, чтобы <tex>V</tex> решил, что слово <tex>x</tex> принадлежит языку;
# <tex>P</tex> не ограничен в вычислительной мощности;
# <tex>V</tex> ограничен полиномиальным временем работы.
}}
[[Файл:IPS.png|250px|thumb|right|Схема интерактивного протокола.]]
<tex>V</tex>, обменивающийся сообщениями с <tex>P</tex>, будем обозначать <tex>V^{P}</tex>.
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
# <tex> \forall x \notin L \Rightarrow P(V^{P}(x) = 1) \le \frac{1}{3} </tex>;<br/>
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.<br/>
}}
{{Определение
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
}}
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\} </tex>.<br/>
}}
{{Определение
|definition = <tex>\mathrm{AM}=\bigcup\limits_{p(n) \in poly} \mathrm{AM} [p(n)] </tex>
Свойство completeness можно достичь, а soundness достичь нельзя.
== Соотношения с другими классами теории сложности ==
{{Теорема
}}
== Язык GNI ==
{{Определение
|definition=
