Изменения
Нет описания правки
Из предыдущей леммы мы получили семейство схем полиномиального размера <tex>C_1, \ldots, C_n, \ldots </tex> Запустим схему <tex>C_m</tex> на <tex>\phi_{xy}</tex>, где <tex>m=n-|x|-|y|</tex>. Эта схема вернет нам такое значение <tex>z</tex>, что <tex>\phi(x,y,z)=1</tex>, если <tex>\phi(x,y,z)</tex> удовлетворима для заданных <tex>x</tex> и <tex>y</tex>, или же последовательность нулей. <br>
Тогда определение языка <tex>L</tex> можно переписать: <tex>L = \{x \bigm| \forall y \ \phi(x, y, C_m(\phi_{xy}))\}</tex>.<br>
Рассмотрим язык <tex>L_1 = \{x\bigm|\exists G \ \forall y \ \phi(x, y, G(x, y , \phi_{xy}))\}</tex>. <br>
Покажем, что <tex>L=L_1</tex>:
*<tex> L \subset L_1</tex><br>
Мы докажем это утверждение, если покажем, что если какое-то слово не принадлежит <tex>L</tex>, то оно не принадлежит и <tex>L_1</tex>.<br>
Пусть <tex>\exists y \ \forall z \ \phi(x,y,z)=0 \Rightarrow \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(x, y , \phi_{xy}))\}</tex>. Следовательно, <tex>L \in \Sigma_2</tex>.
}}
[[Категория: Теория сложности]]
