Изменения

# <mathtex>IP \subset PS</mathtex>Рассмотрим язык <mathtex>L \in IP</mathtex>. Чтобы детерменированная машина Тьюринга <mathtex>m</mathtex> могла установить принадлежность слова <mathtex>x</mathtex> языку <mathtex>L</mathtex>, ей нужно перебрать все ответы <mathtex>P</mathtex> и вероятностные ленты <mathtex>V</mathtex>, просимулировав <mathtex>V</mathtex> с этими данными. Ясно, что эти действия потребуют не более <mathtex>p(|x|)</mathtex> памяти, а значит <mathtex>L \in PS</mathtex>.# <mathtex>PS \subset IP</mathtex>Докажем, что язык <tex>TQBF \in IP</tex>. Этого достаточно, так как <tex>TQBF \in PSC</tex>. Введем следующую арифметизацию булевых формул с кванторами:* <tex>\lnot x \to 1-X</tex>* <tex>x \land y \to XY</tex>* <tex>x \lor y \to 1-(1-X)(1-Y)</tex>* <tex>\exists x \varphi(x) \to \sum_{X=0}^{1} \varPhi(X)</tex>* <tex>\forall x \varphi(x) \to \prod_{X=0}^{1} \varPhi(X)</tex>Результат этого выражения будет ненулевым в том и только в том случае, если исходная формула была истина.