Изменения
Нет описания правки
<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>
Что такое существует <tex>\exists{z что пси от х игрик }:\psi{(x,y,z)}</tex>? Обозначим пары <tex><x,y></tex>, для которых такой <tex>z </tex> существует как какой нибудь язык L1 Рассмотрим <tex>L_1</tex>. <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>
