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