Изменения
→Доказательство
Существует C_n для любого fi (для любого x fi(x)=0 <=>C_n(fi)=0).
Рассмотрим язык <tex>L\in Pi_2</tex>. Это значитозначает, что <tex>x\in L <=> для любого \Leftrightarrow \forall{y существует } \exists{z такой что кси}: \psi{(x,y,x)}</tex> Рассмотрим <tex>L_1 = {<x,y>|\exists{z}: \psi{(x,y,z)}}</tex> <tex>L_1 \in NP </tex> по определению <tex>NP</tex> <tex>L={x|для любого \forall{y } <x,y>\in {L_1}}</tex> Нужно доказать что <tex>L\in \Sigma_1</tex><tex>L_1\in NP => \Rightarrow L_1 <=SAT \le{}_mSAT по карпу с помощью f, т.е. L={x|для любого y f(<x,y>)\in SAT}
f(<x,y>)\in SAT это значит, что для некоторого набора формул выполняется для всего набора, если предположить, что L={x|для любого y C_n(f(<x,y>))=1}
