Изменения
Нет описания правки
== Доказательство ==
Пусть есть логические схемы для <tex>NP</tex> (для любой задаче задачи из NP).Зафиксируем любую задачу из <tex>NP</tex>. Например пусть <tex>SAT</tex> разрешается логическими схемами <tex> C_1...C_n... </tex> (<tex>SAT</tex> с одним битом разрешается логической схемой <tex>C_1</tex>, <tex>SAT</tex> с двумя переменными логической схемой <tex>C_2</tex> и так далее).
Что значит разрешается логической схемой? Это значит что если на вход логической схеме подать каким-то логичным образом закодированную формулу, то на выходе получется логичным образом в виде 0 и 1 закодированный ответ - имеется разложение или нет. И причем размер этой логической схемы <tex>|C_n|\le p(n) </tex>, где <tex>p</tex> - какой-то полином от <tex>n</tex>.
Нужно доказать что <tex>L\in \Sigma_1</tex>
Что такое <tex><x,y> \in subset{L1 }</tex>?
Если <tex>L_1\in{} NP \Rightarrow тоL_1 \le{}_m SAT</tex> по карпу с помощью <tex>f</tex>, т.е. <tex>L=\{x|\forall{y} f(<x,y>)\in{SAT}\}</tex>
<tex>f(<x,y>)\subset{SAT}</tex> - для некоторого набора логических схем это означает выполнимость всего этого набора. Если предположить, что набор этих схем нам известен то получится что <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\}</tex> где <tex>n</tex>- длина входа <tex><x,y></tex>.
Требуется откуда то взять этот набор. Его можно угадать, используя квантор "<tex>\exists{}</tex>" снаружи.Cn он <tex>C_n</tex> существует по предположению что <tex>NP </tex> входит в <tex>P/poly </tex> т.е.
<tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(<x,y>))=1\}</tex>
Что такое Cn Решает SAT? Нам разрешается использовать только Запишем это используя квантор для любого"<tex>\forall{}</tex>".
<tex>C_n</tex> решает <tex>SAT</tex> <tex>\Leftrightarrow</tex> если <tex>\forall{\varphi} \forall{x} (fi(x)=1 \Rightarrow C_n(fi)=1)</tex>
Воспользуемся самосведением <tex>SAT</tex>: <tex>L=\{x|\exists{C1,C2,..,Cn} - набор логических схем для SAT и\forall{y} C_n(f(<x,y>))=1\}</tex>, где - <tex>C1,C2,..,Cn</tex> набор логических схем для <tex>SAT</tex>.
Внутри будем проверять используемый набор
