Просмотр исходного текста страницы Теорема Шамира

{{Теорема
|author=Шамир
|statement=<tex>\mathrm{IP} = \mathrm{PS}</tex>
|proof=
* <tex>\mathrm{IP} \subset \mathrm{PS}</tex>
Рассмотрим язык <tex>L \in \mathrm{IP}</tex>. Пусть <tex>V</tex> {{---}} ''Verifier'', соответствующий <tex>L</tex>, <tex>p(n)</tex> {{---}} время его работы, <tex>f(n)</tex> {{---}} количество его запросов к ''Prover'' 'у. Напишем программу, распознающую язык <tex>L</tex> на полиномиальной памяти.
 <tex>U(x)</tex>
     <tex>n \leftarrow |x|</tex>
     '''for''' <tex>P \leftarrow Prover[f(n), p(n)]</tex>    //(1)
         <tex>count \leftarrow 0</tex>
         '''for''' <tex>r \in \{0, 1\}^{p(n)}</tex>    //(2)
             '''if''' <tex>V(x, r)\bigm{|}_{P} = 1</tex>
                 <tex>count</tex>++
         '''if''' <tex dpi = "160">\frac{count}{2^{p(n)}} \ge \frac{2}{3}</tex>
             '''return''' 1
     '''return''' 0

В цикле <tex>(1)</tex> перебираются все ''Prover'' 'ы, которые отвечают на <tex>f(n)</tex> запросов, каждый ответ имеет размер <tex>p(n)</tex>. В цикле <tex>(2)</tex> перебираются все вероятностные ленты размера <tex>p(n)</tex>. Так как <tex>V</tex> {{---}} корректен, то если нашелся ''Prover'', при котором <tex>V</tex> допускает слово с вероятностью, большей <tex>\frac{2}{3}</tex>, то данное слово принадлежит <tex>L</tex>, иначе {{---}} не принадлежит. Очевидно, что данная программа требует полином дополнительной памяти. Значит <tex>L \in \mathrm{PS}</tex>, следовательно <tex>\mathrm{IP} \subset \mathrm{PS}</tex>.
* <tex>\mathrm{PS} \subset \mathrm{IP}</tex>

Докажем, что <tex>\mathrm{TQBF} \in \mathrm{IP}</tex>. Так как <tex>\mathrm{TQBF} \in \mathrm{PSC}</tex>, то из этого будет следовать, что <tex>\mathrm{PS} \subset \mathrm{IP}</tex>.

Пусть дана формула <tex>Q_1 \ldots Q_m \phi(x_1, \ldots ,x_m)</tex>. В процессе [[Арифметизация булевых формул с кванторами|арифметизации]] она перейдет в <tex>R_1 \ldots R_m A_\phi(x_1,\ldots,x_m)</tex>. Воспользуемся протоколом, описанным в [[Лемма о соотношении coNP и IP|доказательстве принадлежности #SAT к классу IP]]. Для этого необходимо, чтобы степень полиномов <tex>A_i(x_{i+1})</tex> была полиномиальной относительно длины входа. Преобразуем выражение с помощью оператора линеаризации к виду <tex>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_\phi(x_1,\ldots,x_m)</tex>. Размер новой формулы не превосходит квадрата исходной, степень полиномов не превосходит двух. Тогда, используя условия, описанные в [[Арифметизация булевых формул с кванторами|леммах 2 и 3]], для проверки ответов, присылаемых ''Prover'' 'ом, можно построить искомый протокол. Значит <tex>\mathrm{TQBF} \in \mathrm{IP}</tex>, следовательно <tex>\mathrm{PS} \subset \mathrm{IP}</tex>.
}}