Изменения

{{Теорема|author== Формулировка ==Шамир'''[[Класс IP|statement=<tex>\mathrm{IP]]''' } = '''[[Класс \mathrm{PS}</tex>|PS]]'''== Доказательство =proof=# * <tex>\mathrm{IP } \subset \mathrm{PS}</tex>Рассмотрим язык <tex>L \in \mathrm{IP}</tex>. Чтобы детерменированная машина Тьюринга Пусть <tex>mV</tex> могла установить принадлежность слова {{---}} ''Verifier'', соответствующий <tex>xL</tex> языку , <tex>Lp(n)</tex>{{---}} время его работы, ей нужно перебрать все ответы <tex>Pf(n)</tex> и вероятностные ленты {{---}} количество его запросов к ''Prover'' 'у. Напишем программу, распознающую язык <tex>VL</tex>, просимулировав на полиномиальной памяти. <tex>VU(x)</tex> с этими данными. Ясно, что эти действия потребуют не более <tex>p(n \leftarrow |x|)</tex> памяти, а значит '''for''' <tex>L P \in PSleftarrow Prover[f(n), p(n)]</tex>. //(1)# <tex>PS count \subset IPleftarrow 0</tex>Докажем, что язык '''for''' <tex>TQBF r \in IP\{0, 1\}^{p(n)}</tex>. Этого достаточно //(2) '''if''' <tex>V(x, так как r)\bigm{|}_{P} = 1</tex> <tex>count</tex>++ '''if''' <texdpi = "160">TQBF \in PSCfrac{count}{2^{p(n)}} \ge \frac{2}{3}</tex>. '''return''' 1 '''return''' 0

Введем следующую арифметизацию булевых формул с кванторами:* В цикле <tex>\lnot x \to (1-X)</tex>* перебираются все ''Prover'' 'ы, которые отвечают на <tex>x \land y \to XYf(n)</tex>* запросов, каждый ответ имеет размер <tex>x \lor y \to X+Y-XY = 1-p(1-Xn)</tex>. В цикле <tex>(1-Y2)</tex>* перебираются все вероятностные ленты размера <tex>\exists x \varphip(xn) </tex>. Так как <tex>V</tex> {{---}} корректен, то если нашелся ''Prover'', при котором <tex>V</tex> допускает слово с вероятностью, большей <tex>\to frac{2}{3}</tex>, то данное слово принадлежит <tex>L</tex>, иначе {{---}} не принадлежит. Очевидно, что данная программа требует полином дополнительной памяти. Значит <tex>L \sumin \limits_mathrm{X=0PS}^</tex>, следовательно <tex>\mathrm{1IP} A_\varphi(X)subset \mathrm{PS}</tex>.* <tex>\forall x \varphi(x) \to mathrm{PS} \prodsubset \limits_{X=0}^mathrm{1IP} A_\varphi(X)</tex>Результат этого выражения будет ненулевым в том и только в том случае, если исходная формула была истина.

Рассмотрим пример: Докажем, что <tex>\varphi=\forall x_1 mathrm{TQBF} \forall x_2 in \cdots \forall x_mathrm{k-1IP} \exists x_k (x_k \lor \lnot x_k)</tex> . Так как <tex>A_\varphi = \prod\limits_mathrm{X_1=0}^{1TQBF}\prodin \limits_mathrm{X_2=0PSC}^</tex>, то из этого будет следовать, что <tex>\mathrm{1PS}\cdots subset \prod\limits_mathrm{X_{k-1}=0}^{1IP}</tex>. Пусть дана формула <tex>Q_1 \sumldots Q_m \limits_{X_k=0}^1phi(1-X_k(1-X_kx_1, \ldots ,x_m)) = 2^{2^{</tex>. В процессе [[Арифметизация булевых формул с кванторами|арифметизации]] она перейдет в <tex>R_1 \ldots R_m A_\phi(k-1x_1,\ldots,x_m)}}</tex>. Воспользуемся протоколом, описанным в [[Лемма о соотношении coNP и IP|доказательстве принадлежности #SAT к классу IP]]. Для записи этого числа нужно необходимо, чтобы степень полиномов <tex>2^A_i(x_{(k-i+1})}</tex> битбыла полиномиальной относительно длины входа. Если Преобразуем выражение с помощью оператора линеаризации к виду <tex>k R_1 L_1 \ldots R_i L_1 L_2 \ldots L_i \ldots R_m L_1 L_2 \ldots L_m A_\gg phi(x_1,\logldots,x_m)</tex>. Размер новой формулы не превосходит квадрата исходной, степень полиномов не превосходит двух. Тогда, используя условия, описанные в [[Арифметизация булевых формул с кванторами|леммах 2 и 3]], для проверки ответов, присылаемых ''Prover'' 'ом, можно построить искомый протокол. Значит <tex>\mathrm{TQBF} \in \varphi|mathrm{IP}</tex>, его невозможно передать за полиномиальное относительно длины исходной формулы времяследовательно <tex>\mathrm{PS} \subset \mathrm{IP}</tex>.}}