Изменения
→Доказательство
Нужно доказать что <tex>L\in \Sigma_1</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>)\in {SAT }</tex> - это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что <tex>L={x|для любого \forall{y } C_n(f(<x,y>))=1}</tex>
Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его.
Так как <tex>NP \in {} P/poly </tex> то </tex>L={x|существует \exists{C_n}: C_n решает SAT и для любого \forall{y } C_n(f(<x,y>))=1}</tex> Что означает <tex>C_n </tex> решает <tex>SAT</tex>? Нужно переписать с квантором для любого.<tex>C_n решает SAT <=> для любого \Leftrightarrow \forall{\fi для любого } \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>
Внутри будем проверять используемый набор
для любого fi (С_|fi|(fi)=0 => для любого x fi(x)=0) (C_|fi|(fi)=1 => fi|_x1=0 \in SAT или fi|_x1=1 \in SAT)
