Изменения

Иначе, выберем любую переменную <tex>x</tex> из формулы <tex>\phi</tex>, и выполним подстановку <tex>x = 0</tex>. Получим формулу <tex>\phi_0</tex>. Если <tex>\phi_0 \in SAT</tex> (так как по условию теоремы <tex>SAT \in P/poly</tex>, такую проверку можно сделать за полиномиальное время, вычислив соответствующую схему), то мы свели задачу к аналогичной с меньшим числом переменных. В противном случае, сведение выполняется подстановкой <tex>x = 1</tex>. Мы получили программу, работающую за полиномиальное время, а так как <tex>P \in P/poly</tex>, то и семейство требуемых схем.

}}

{{Теорема

Если <tex>NP \subset P/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.

|proof=

Рассмотрим формулу <tex>\psi(x, z) = \exists y</tex> <tex>\phi(x, y, z)</tex> как экземпляр задачи <tex>SAT</tex>.<br/>

Покажем что <tex>(\forall x</tex> <tex> \phi(x,D_{|\psi(x, z)|}(\psi(x, z)), z)</tex> <tex>)\Leftrightarrow</tex> <tex>(\exists G : </tex> <tex> \forall x</tex> <tex>\phi(x, G(\psi(x, z)), z))</tex>.

<br>Очевидно, из первого следует второе, так как <tex>\exists G = D_{|\psi(x, z)|}</tex>.

Если первое ложно, то <tex>\exists x = x_0 : </tex> <tex>\forall y</tex> <tex>\phi(x, y, z) = 0</tex>, а значит <tex>\forall G </tex> <tex>\exists x = x_0 : \phi (x, G(\psi(x, z)), z)</tex>, то есть второе ложно.

}}