210
правок
Изменения
Нет описания правки
[[Файл:IPS.png|600px|thumb|right|Схема интерактивного протокола.]]
'''Замечания''':# <tex>V</tex>, обменивающийся сообщениями с фиксированным <tex>P</tex>, обозначим <tex>V_{P}</tex>.# <tex> P </tex> может быть и вероятностной и детерминированной машиной Тьюринга. Так как он имеет неограниченные вычислительные ресурсы, то на каждом ходу он может выбрать такие вероятностные данные и произвести вычисления с ними, что они максимизируют вероятность принятия слова <tex> V </tex>.# С другой стороны, для <tex> V </tex> важно быть вероятностной программой, так как иначе он будет принимать или отвергать слова с вероятностью <tex> 1 </tex>. И пользуясь предыдущим фактом, получим, что <tex> V_{P} </tex> всегда принимает слова из <tex> L </tex>. # Так как <tex> V </tex> может писать и читать полиномиальное число символов, то длина сообщений между <tex> V </tex> и <tex> P </tex> есть полином от длины <tex> x </tex>.
Интерактивные протоколы делятся на два типа в зависимости от доступа <tex>P</tex> к вероятностной ленте <tex>V</tex>:
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \in L \Rightarrow \exists P : \mathbb{P}(V_{P}(x) = 1) \geqslant \alpha c </tex>, то говорят, что он обладает свойством ''' completeness ''' (русск. ''полнота'') равным <tex> \alpha </tex>.
}}
Если completeness равно <tex>c = 1</tex>('''perfect completeness'''), то это означает, что никакое верное утверждение не отклоняется <tex> V </tex>.
{{Определение
|definition =
Если для интерактивного протокола выполняется <tex> \forall x \notin L \Rightarrow \forall P : \mathbb{P}(V_{P}(x) = 1) \leqslant 1 - \alpha s </tex>, то говорят, что он обладает свойством ''' soundness ''' (русск. ''достоверность'') равным <tex> \alpha </tex>.
}}
Если soundness равно <tex> s = 1 </tex>('''perfect soundness'''), то это означет, что если утверждение ложно, то никакой <tex>P</tex> не может убедить <tex>V</tex>, что утверждение истино. Свойство completeness можно достичьВ этом случае мы получем класс <tex> \mathrm{NP} </tex>. Потому что <tex> x \in L </tex> тогда и только тогда, если существует последовательность случайных вопросов, а soundness достичь нельзягенерируемых <tex> V </tex>, и последовательность ответов <tex> P </tex>, которые убеждают <tex> V </tex> в том, что <tex> x \in L </tex>. Обратное утверждение сохраняется по предположению идеальной достоверности.
{{Определение
|definition =
<tex>\mathrm{IP}[f] </tex> (''Interactive Polynomial time'') <tex> = \{L \mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex>
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins).
# completeness <tex> c \geqslant 2/{3} </tex>.# soundness <tex> s \geqslant 2 /{3} </tex>.
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.
}}
|definition = <tex>\mathrm{IP}=\bigcup\limits_{p(n) \in poly} \mathrm{IP} [p(n)] </tex>
}}
То есть <tex> \mathrm{IP}</tex> (''Interactive Polynomial time'') {{---}} множество языков разрешимых интерактивным протоколом , таких, что число сообщений ограничено полиномом от длины слова и <tex>V</tex> должен решить лежит ли слово в языке с вероятностью ошибки не более <tex>1/{3}</tex>.
Язык <tex>\mathrm{AM}</tex> (''Arthur–Merlin games'') отличается от <tex>\mathrm{IP}</tex> лишь тем, что <tex>P</tex> может видеть вероятностную ленту <tex>V</tex>.
<tex>\mathrm{AM}[f] = \{L \mid \exists </tex> интерактивный протокол <tex>\langle P, V \rangle : </tex>
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins).
# completeness <tex> c \geqslant 2/{3} </tex>.# soundness <tex> s \geqslant 2 /{3} </tex>.
# число раундов интерактивного протокола <tex> O(f(n)), n = |x|\}</tex>.
}}
