Изменения
Нет описания правки
L_1\in NP => L_1 <=SAT по карпу с помощью f, т.е. L={x|для любого y f(<x,y>)\in SAT}
f(<x,y>)\in SAT это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что L={x|для любого y C_n(f(<x,y>))=1}
Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его.
Так как NP \in P/poly
L={x|существует C_n: C_n решает SAT и для любого y C_n(f(<x,y>))=1}
Что означает C_n решает SAT? Нужно переписать с квантором для любого.
C_n решает SAT <=> для любого \fi для любого x (если fi(x)=1 то C_n(fi)=1)
Воспользуемся самосведением SAT L={x|существуют C1C2...Cn - набор логических схем для SAT и для любого y C_n(f(<x,y>))=1}
Внутри будем проверять используемый набор
для любого fi (С_|fi|(fi)=0 => для любого x fi(x)=0) (C_|fi|(fi)=1 => fi|_x1=0 \in SAT или fi|_x1=1 \in SAT)
Если C решает SAT то все хорошо, если нет то зафиксируем формулу на которой не решает. Если выдаст 0 а должна выдать 1 то первое не удолветворяет, если наоборот то обе не удовлетворяет.
для любого fi |fi|=m для любого x_1...любого x_m если C_m(fi)=0 => fi(x_1)=0 иначе C_m-1(fi|_x_1=0)=0 => fi|_x1=0(x2)=0
