Изменения
Нет описания правки
Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
Если <tex>\exists y \ \forall z \ \phi(x,y,z)=0 </tex>, тогда <tex>\nexists G \ \forall y \ \phi(x, y, G(\phi_{xy}))=1</tex>. <br>
Таким образом <tex>L =\{x\bigm|\exists G, |G| < p(|x|) \ \forall y, |y|<p(|x|) \ \phi(x, y, G(\phi_{xy})) = 1\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>. Значит, <tex>\mathrm{\Pi_2} \subset \mathrm{\Sigma_2} </tex>.<br>Докажем теперь, что <tex>\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} </tex>.Рассмотрим язык <tex>L \in \mathrm{\Sigma_2}</tex>: <tex>L \in \mathrm{\Sigma_2} \Rightarrow \overline{L} \in \mathrm{\Pi_2} \Rightarrow \overline{L} \in \mathrm{\Sigma_2} \Rightarrow L \in \mathrm{\Pi_2}</tex>. Получается, что <tex>\mathrm{\Sigma_2} \subset \mathrm{\Pi_2} </tex>.Итого, <tex>\mathrm{\Sigma_2} = \mathrm{\Pi_2} </tex>.
}}
[[Категория: Теория сложности]]
