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

Теорема (Шамир):

[math]\mathrm{IP} = \mathrm{PS}[/math]

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

[math]\triangleright[/math]

[math]\mathrm{IP} \subset \mathrm{PS}[/math] Рассмотрим язык [math]L \in \mathrm{IP}[/math]. Пусть [math]V[/math] — Verifier, соответствующий [math]L[/math], [math]p(n)[/math] — время его работы, [math]f(n)[/math] — количество его запросов к Prover 'у. Напишем программу, распознающую язык [math]L[/math] на полиномиальной памяти. [math]U(x)[/math] [math]n \leftarrow |x|[/math] for [math]P \leftarrow Prover[f(n), p(n)][/math] //(1) [math]count \leftarrow 0[/math] for [math]r \in \{0, 1\}^{p(n)}[/math] //(2) if [math]V(x, r)\bigm{|}_{P} = 1[/math] [math]count[/math]++ if [math]\frac{count}{2^{p(n)}} \ge \frac{2}{3}[/math] return 1 return 0 В цикле [math](1)[/math] перебираются все Prover 'ы, которые отвечают на [math]f(n)[/math] запросов, каждый ответ имеет размер [math]p(n)[/math]. В цикле [math](2)[/math] перебираются все вероятностные ленты размера [math]p(n)[/math]. Так как [math]V[/math] — корректен, то если нашелся Prover, при котором [math]V[/math] допускает слово с вероятностью, большей [math]\frac{2}{3}[/math], то данное слово принадлежит [math]L[/math], иначе — не принадлежит. Очевидно, что данная программа требует полином дополнительной памяти. Значит [math]L \in \mathrm{PS}[/math], следовательно [math]\mathrm{IP} \subset \mathrm{PS}[/math]. [math]\mathrm{PS} \subset \mathrm{IP}[/math] Докажем, что [math]\mathrm{TQBF} \in \mathrm{IP}[/math]. Так как [math]\mathrm{TQBF} \in \mathrm{PSC}[/math], то из этого будет следовать, что [math]\mathrm{PS} \subset \mathrm{IP}[/math]. Пусть дана формула [math]Q_1 \ldots Q_m \phi(x_1, \ldots ,x_m)[/math]. В процессе арифметизации она перейдет в [math]R_1 \ldots R_m A_\phi(x_1,\ldots,x_m)[/math]. Воспользуемся протоколом, описанным в доказательстве принадлежности #SAT к классу IP. Для этого необходимо, чтобы степень полиномов [math]A_i(x_{i+1})[/math] была полиномиальной относительно длины входа. Преобразуем выражение с помощью оператора линеаризации к виду [math]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)[/math]. Размер новой формулы не превосходит квадрата исходной, степень полиномов не превосходит двух. Тогда, используя условия, описанные в леммах 2 и 3, для проверки ответов, присылаемых Prover 'ом, можно построить искомый протокол. Значит [math]\mathrm{TQBF} \in \mathrm{IP}[/math], следовательно [math]\mathrm{PS} \subset \mathrm{IP}[/math].

[math]\triangleleft[/math]

,