Изменения

Пусть дана формула <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>.