1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Теорема|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[[Класс IPf(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{|IP]]}_{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>. Размер новой формулы не превосходит квадрата исходной, степень полиномов не превосходит двух. Тогда, используя условия, описанные в [[Класс PSАрифметизация булевых формул с кванторами|PSлеммах 2 и 3]], для проверки ответов, присылаемых ''Prover'''ом, можно построить искомый протокол. Значит <tex>\mathrm{TQBF} \in \mathrm{IP}</tex>, следовательно <tex>\mathrm{PS} \subset \mathrm{IP}</tex>.== Доказательство ==}}
