Изменения
Нет описания правки
== Доказательство ==
Пусть есть логические схемы для NP. Например C_1...C_n... SAT который кодирует i символов, разрешимых логической схемой C_i. Размер |C_i|<=p(n).
Это означает что для фиксированного n найдется такая логическая схема C_n что для любого fi (fi \in SAT & |fi|=n <=> C_n(fi)=1)
Существует C_n для любого fi (для любого x fi(x)=0 <=>C_n(fi)=0).
Рассмотрим язык L\in Pi_2. Это значит, что x\in L <=> для любого y существует z такой что кси(x,y,x)
Рассмотрим L_1={<x,y> | существует z кси(x,y,z)}
L_1 \in NP по определению NP
L={x|для любого y <x,y>\in L_1}
Нужно доказать что L\in \Sigma_1
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}
