1632
правки
Изменения
м
Попобуем Попробуем построить схемы <tex>C_n^1, \ldots, C_n^n</tex>, работающие следующим образом:
rollbackEdits.php mass rollback
|proof=
Пусть нам дана формула <tex>\phi</tex> с <tex>n</tex> переменными.<br>
*<tex>C_n^1(\phi) = 1 \Leftrightarrow \exists x_2,\ldots, x_n: \phi(1,x_2, \ldots, x_n)=1</tex>;
*<tex> \ldots </tex>
*<tex>L_1 \subset L</tex>
Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <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>.
}}
[[Категория: Теория сложности]]
