Изменения
Нет описания правки
<tex> \exists{C_n} \forall{\varphi{}} (\forall{x} формулы длины n \varphi{(x)}=0 \Leftrightarrow C_n(\varphi{})=0)</tex>.
Рассмотрим язык <tex>L\in \Pi_2</tex>. Это означает, что <tex>x\in L \Leftrightarrow \forall{y} \exists{z}: \psi{(x,y,x)}</tex>
Что такое существует z что пси от х игрик z? Обозначим пары <x,y>, для которых такой z существует как какой нибудь язык L1 Рассмотрим <tex>L_1 = \{<x,y>|\exists{z}: \psi{(x,y,z)}\}</tex>. Заметим что <tex>L_1 \in NP</tex> по определению <tex>NP</tex>
Итого L это множество слов <tex>L={x|\forall{y} <x,y>\in{L_1}}</tex>
Нужно доказать что <tex>L\in \Sigma_1</tex>
Что такое <x,y> \in L1 ?
Если <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>
Что такое f(<x,y>)\in SAT ?
<tex>f(<x,y>)\in{SAT}</tex> - это значит, что для некоторого набора булевых(логических) схем, выполнимость всего этого набора, если предположить, что набор этих схем нам известен то получится что <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\}</tex> где n- длина входа <x,y>
Нам надо откуда то взять этот набор. Мы можем его угадать используя квантор существует снаружи.
Cn он существует по предположению что NP входит в P/poly т.е.
<tex>L=\{x|\exists{C_n}: C_n решает SAT и \forall{y} C_n(f(<x,y>))=1\}</tex>
Что такое Cn Решает SAT? Нам разрешается использовать только квантор для любого.
<tex>C_n</tex> решает <tex>SAT</tex> <tex>\Leftrightarrow</tex> если <tex>\forall{\varphi} \forall{x} (fi(x)=1 \Rightarrow C_n(fi)=1)</tex>
Рассмотрим <tex>L_1 = \{<x,y>|\exists{z}: \psi{(x,y,z)}\}</tex>
Но надо откуда-то взять этот набор. Можно его угадать, используя квантор существует. Добавим его.
Что означает <tex>C_n</tex> решает <tex>SAT</tex>? Нужно переписать с квантором для любого.
Воспользуемся самосведением <tex>SAT</tex>: <tex>L=\{x|\exists{C1,C2,..,Cn} - набор логических схем для SAT и\forall{y} C_n(f(<x,y>))=1\}</tex>
