Теорема Шамира

Формулировка

IP = PS

Доказательство

1. [math]IP \subset PS[/math]

Рассмотрим язык [math]L \in IP[/math]. Чтобы детерменированная машина Тьюринга [math]m[/math] могла установить принадлежность слова [math]x[/math] языку [math]L[/math], ей нужно перебрать все ответы [math]P[/math] и вероятностные ленты [math]V[/math], просимулировав [math]V[/math] с этими данными и посчитав вероятность допуска. Ясно, что эти действия потребуют не более [math]p(|x|)[/math] памяти, а значит [math]L \in PS[/math].

1. [math]PS \subset IP[/math]

Докажем, что язык [math]TQBF \in IP[/math]. Этого достаточно, так как [math]TQBF \in PSC[/math].

Введем следующую арифметизацию булевых формул с кванторами:

• [math]\lnot x \to 1-X[/math]
• [math]x \land y \to XY[/math]
• [math]x \lor y \to X+Y-XY = 1-(1-X)(1-Y)[/math]
• [math]\exists x \varphi(x) \to \sum\limits_{X=0}^{1} A_\varphi(X)[/math]
• [math]\forall x \varphi(x) \to \prod\limits_{X=0}^{1} A_\varphi(X)[/math]

Результат этого выражения будет ненулевым в том и только в том случае, если исходная формула была истина.

Рассмотрим пример:

[math]\varphi=\forall x_1 \forall x_2 \cdots \forall x_{k-1} \exists x_k (x_k \lor \lnot x_k)[/math]
[math]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)}}[/math]

Для записи этого числа нужно [math]2^{(k-1)}[/math] бит. Если [math]k \gg \log|\varphi|[/math], это число невозможно передать за полиномиальное относительно длины исходной формулы время. Чтобы избежать таких больших чисел, приходится проводить все операции по какому-нибудь простому модулю [math]p[/math].

Итак, интерактивный протокол.

• P выбирает простое [math]p[/math] и [math]k \equiv A_\psi \pmod{p}[/math] и посылает их V ([math]p[/math] посылается вместе с его сертификатом простоты).
• V проверяет [math]p[/math] на простоту, а [math]k[/math] на неравенство нулю.