Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
{{Определение
|definition =
<tex>\mathrm{IP}[f]} = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
# <tex>P</tex> не имеет доступа к вероятностной ленте <tex>V</tex> (private coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
{{Определение
|definition =
<tex>\mathrm{AM}[f]} = \{L\bigm|\exists \langle V, P \rangle : </tex> <br/>
# <tex>P</tex> может читать вероятностную ленту <tex>V</tex> (public coins);
# <tex> \forall x \in L \Rightarrow P(V(x) = 1) \ge \frac{2}{3} </tex>;<br/>
{{Теорема
|statement=<tex>\mathrm{BPP} \subset \mathrm{IP}[0]}</tex>.
|proof=
<tex>V</tex> сам по себе является вероятностной машиной Тьюринга и поэтому может разрешить язык из <tex>\mathrm{BPP}</tex> не прибегая к общению с <tex>P</tex>.
{{Теорема
|statement=<tex>\mathrm{NP} \subset \mathrm{IP}[1]}</tex>.
|proof=
Для разрешения языка из <tex>\mathrm{NP}</tex> будем использовать следующий протокол:
{{Теорема
|statement=<tex>\mathrm{GNI} \in \mathrm{IP}[1]}</tex>.
|proof=
Будем использовать следующий алгоритм для <tex>V</tex>:
# Если мы ещё не вернули <tex>0</tex>, то вернём <tex>1</tex>.
Покажем, что это удовлетворяет ограничениям на <tex>\mathrm{IP}[1]}</tex>.
Во-первых, очевидно, что число раундов не превосходит двух. <br/>
Рассмотрим теперь случаи
