Изменения

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

Если Зададимся формулой <tex>\phi</tex> не содержит переменных, то есть является тождественной единицей, решение задачи тривиально.Иначе, выберем любую переменную Определим семейство схем <tex>C_n^1 ... C_n^n</tex> так: схема <tex>xC_n^i</tex> из формулы будет принимать на вход формулу <tex>\phi</tex>, и выполним подстановку <tex>x = 0i-1</tex>бит <tex>b_1 . Получим формулу .. b_{i-1}</tex>, и возвращать <tex>\phi_01</tex>. Если тогда и только тогда, когда существует набор переменных, удовлетворяющий <tex>\phi_0 \in SATphi</tex> (так как по условию теоремы , такой что <tex>SAT \in \mathrmx_1 = b_1 ... x_{i-1}=b_{Pi-1}</tex> и <tex>x_i=1</polytex>. Так как задача определения выходного значения таких схем принадлежит <tex>NP</tex>, такую проверку можно сделать за полиномиальное времято такие схемы существуют и имеют полиномиальный размер. Очевидно, вычислив соответствующую схему)что если формула <tex>\phi</tex> удовлетворима, то мы свели задачу к аналогичной с меньшим числом переменных. В схема <tex>C_n^i</tex> вернет значение <tex>i</tex>-й переменной удовлетворяющего набора, в противном случае, сведение выполняется подстановкой схема вернет <tex>x = 10</tex>. Мы получили программу, работающую за полиномиальное время, а так как Теперь используем выходы схем <tex>\mathrmC_n^1...C_n^{Pi-1} \in \mathrm</tex> как вход <tex>b_1...b_{Pi-1}</tex> схемы <tex>C_n^i</polytex> и получим схему с <tex>n</tex>выходами, то и семейство требуемых схемвозвращающую требуемые набор.