Изменения
→Доказательство
Это означает что для фиксированного <tex>n</tex> <tex>\exists{}</tex> такая логическая схема <tex>C_n</tex>, что <tex>\forall{}\varphi{} (\varphi{} \in{} SAT |\varphi{}|=n \Leftrightarrow C_n(\varphi{})=1)</tex>
Рассмотрим язык <tex>L\in Pi_2</tex>. Это означает, что <tex>x\in L \Leftrightarrow \forall{y} \exists{z}: \psi{(x,y,x)}</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>? Нужно переписать с квантором для любого.
