33
правки
Изменения
Нет описания правки
Рассмотрим язык <tex>L\in \Pi_2</tex>. Это означает, что <tex>x\in L \Leftrightarrow \forall{y} \exists{z}: \psi{(x,y,x)}</tex>
Обозначим пары <tex><x,y></tex>, для которых такой <tex>z</tex> существует как какой нибудь язык <tex>L_1</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><x,y> \subset{L_1}</tex>?'''
Если <tex>L_1\in{} NP</tex> то <tex>\Rightarrow L_1 \le{}_m SAT</tex> с помощью <tex>f</tex>, т.е. <tex>L=\{x|\forall{y} f(<x,y>)\in{SAT}\}</tex>
'''Что такое "<tex>f(<x,y>)\subset{SAT}</tex>"?'''
<tex>f(<x,y>)\subset{SAT}</tex> - для некоторого набора логических схем это означает выполнимость всего этого набора. Если предположить, что набор этих схем нам известен то получится что <tex>L=\{x|\forall{y} C_n(f(<x,y>))=1\}</tex> где <tex>n</tex>- длина входа <tex><x,y></tex>.
