69
правок
Изменения
Нет описания правки
{{Лемма
|statement= Пусть <tex>SAT \in \mathrm{P}/poly </tex>, тогда для любой формулы <tex>\phi</tex> с <tex>n</tex> переменными, существует семейство такая последовательность схем полиномиального размера <tex>D_nC_n^1...C_n^n</tex> таких, что для любой формулы <tex>\phi \in SATC_n^i</tex> c возвращает значение <tex>ni</tex> переменными-й переменной в наборе переменных, удовлетворяющих <tex>D_{n}(\phi)</tex> выводит набор значений, удовлетворяющий формулеесли <tex>\phi \in SAT</tex>, или последовательность нулей <tex>0</tex> если <tex>\phi \not \in SAT</tex>
|proof=
Зададимся формулой <tex>\phi</tex>. Определим семейство схем <tex>C_n^1 ... C_n^n</tex> так: схема <tex>C_n^i</tex> будет принимать на вход формулу <tex>\phi</tex> и <tex>i-1</tex> бит <tex>b_1 ... b_{i-1}</tex>, и возвращать <tex>1</tex> тогда и только тогда, когда существует набор переменных, удовлетворяющий <tex>\phi</tex>, такой что <tex>x_1 = b_1 ... x_{i-1}=b_{i-1}</tex> и <tex>x_i=1</tex>. Так как задача определения выходного значения таких схем принадлежит <tex>NP</tex>, то такие схемы существуют и имеют полиномиальный размер. Очевидно, что если формула <tex>\phi</tex> удовлетворима, то схема <tex>C_n^i</tex> вернет значение <tex>i</tex>-й переменной удовлетворяющего набора, в противном случае схема вернет <tex>0</tex>. Теперь используем выходы схем <tex>C_n^1...C_n^{i-1}</tex> как вход <tex>b_1...b_{i-1}</tex> схемы <tex>C_n^i</tex> и получим схему с <tex>n</tex> выходами, возвращающую требуемые набор.
}}
Если <tex>\mathrm{NP} \subset \mathrm{P}/poly</tex>, то <tex>\Sigma_2 = \Pi_2</tex>.
|proof=
}}
[[Категория: Теория сложности]]