Изменения
Нет описания правки
== Доказательство ==
# <tex>IP \subset PS</tex>
Рассмотрим язык <tex>L \in IP</tex>. Чтобы детерменированная машина Тьюринга <tex>m</tex> могла установить принадлежность слова <tex>x</tex> языку <tex>L</tex>, ей нужно перебрать все ответы <tex>P</tex> и вероятностные ленты <tex>V</tex>, просимулировав <tex>V</tex> с этими даннымии посчитав вероятность допуска. Ясно, что эти действия потребуют не более <tex>p(|x|)</tex> памяти, а значит <tex>L \in PS</tex>.
# <tex>PS \subset IP</tex>
Докажем, что язык <tex>TQBF \in IP</tex>. Этого достаточно, так как <tex>TQBF \in PSC</tex>.
<tex>\varphi=\forall x_1 \forall x_2 \cdots \forall x_{k-1} \exists x_k (x_k \lor \lnot x_k)</tex>
<tex>A_\varphi = \prod\limits_{X_1=0}^{1}\prod\limits_{X_2=0}^{1}\cdots \prod\limits_{X_{k-1}=0}^{1}\sum\limits_{X_k=0}^1(1-X_k(1-X_k)) = 2^{2^{(k-1)}}</tex>
Для записи этого числа нужно <tex>2^{(k-1)}</tex> бит. Если <tex>k \gg \log|\varphi|</tex>, его это число невозможно передать за полиномиальное относительно длины исходной формулы время. Чтобы избежать таких больших чисел, приходится проводить все операции по какому-нибудь простому модулю <tex>p</tex>. Итак, интерактивный протокол. * ''P'' выбирает простое <tex>p</tex> и <tex>k \equiv A_\psi \pmod{p}</tex> и посылает их ''V'' (<tex>p</tex> посылается вместе с его сертификатом простоты).* ''V'' проверяет <tex>p</tex> на простоту, а <tex>k</tex> на неравенство нулю.
