Изменения

|statement= Пусть <tex>SAT \in \mathrm{P}/poly </tex>, тогда существует семейство схем полиномиального размера <tex>D_n</tex>, таких, что для любой формулы <tex>\phi \in SAT</tex>, <tex>D_{|\phi|}(\phi)</tex> выводит набор значений, удовлетворяющий формуле.

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

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

Так как <tex>\mathrm{NP } \subset \mathrm{P}/poly</tex>, то <tex>\mathrm{SAT} \in \mathrm{P}/poly}</tex>, то есть для любого <tex>n</tex> . Тогда по лемме найдётся схема семейство схем полиномиального размера <tex> C_nD_n</tex>таких, такая что для любой формулы <tex>C_{|\phi|}(\phi) = \left[\phi \in SAT\right]</tex>.Тогда, найдётся и схема полиномиального размера <tex> D_{|\phi|}</tex>, выдающая для <tex>(\phi \in SAT)</tex> выводит набор значений, удовлетворяющий <tex>\phi</tex>.