|statement= Пусть <tex>\mathrm{SAT} \in \mathrm{P}/poly </tex>. Тогда для любой формулы <tex>\phi</tex> с <tex>n</tex> переменными существует такая последовательность схем полиномиального размера <tex>C_n^1, \ldots, C_n^n</tex>, что <tex>C_n^i</tex> возвращает значение <tex>i</tex>-й переменной в наборе переменных, удовлетворяющих <tex>\phi</tex>, если <tex>\phi \in \mathrm{SAT}</tex>, или <tex>0</tex> если <tex>\phi \not \in \mathrm{SAT}</tex>
|proof=
Зададимся формулой <tex>\phi</tex>. Определим семейство схем схемы следующим образом:*<tex>C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, C_n^nx_n)=1</tex> так: схема ;*<tex>C_n^i\ldots </tex> будет принимать на вход формулу *<tex>C_n^i(\phi</tex> и <tex>, b_1, \ldots, b_{i-1</tex> бит <tex>}) = 1 \Leftrightarrow \exists x_{i+1},\ldots, x_n: \phi(b_1, \ldots, b_{i-1},1,x_{i+1}, \ldots, x_n)=1</tex> и возвращать ;*<tex>1\ldots </tex> тогда и только тогда, когда существует набор переменных, удовлетворяющий *<tex>C_n^n(\phi</tex>, такой что <tex>x_1 = b_1, \ldots, x_b_{in -1}) =1 \Leftrightarrow \phi(b_1, \ldots, b_{in-1}, 1)=1</tex> и .Задача определения возврщаемого значения таких схем {{---}} задача <tex>x_i=1\mathrm{SAT}</tex>. Так как задача определения выходного значения таких схем принадлежит По условию <tex>\mathrm{NPSAT} \in \mathrm{P}/poly </tex>, то следовательно, такие схемы существуют и имеют полиномиальный размеркаждая из них будет полиномиального размера. Очевидно, что если формула Рассмотрим последовательность: <tex>b_1=C_n^1(\phi</tex> удовлетворима), b_2=C_n^2(\phi, b1), \ldots, то схема <tex>b_n=C_n^in(\phi, b_1, \ldots, b_{n-1})</tex> вернет значение . Очевидно, что это будет последовательностью бит, которая удовлетворяет <tex>i\phi</tex>-й переменной удовлетворяющего набора, в противном случае схема вернет или же последовательностью нулей, если <tex>0\phi</tex>удовлетворить нельзя.
}}
