Изменения
Нет описания правки
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Sigma_{i+1}</math> == === Утверждение теоремы ===
Если <math>\Sigma_i = \Sigma_{i+1}</math>, то <math>\Sigma_i = PH</math>.
=== Доказательство ===
Из <math>\Sigma_i = \Sigma_{i+1}</math> очевидным образом следует <math>\Pi_i = \Pi_{i+1}</math>.
Получается, что <math>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_1(\overline{x, y_1}, y_2 \ldots y_{n+1})</math>, откуда следует <math>L \in \Sigma_{n+1} \Rightarrow L \in \Sigma_n</math>, что и требовалось доказать.
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Pi_i</math> ==
=== Утверждение теоремы ===
Если <math>\Sigma_i = \Pi_i</math>, то <math>\Sigma_i = PH</math>.
=== Доказательство теоремы ===
Доказательство аналогично доказательству предыдущей теоремы. Мы снова будем удалять квантор из формулы и получим, что если можно удалить один квантор, то можно удалить их все.
Докажем, что <math>\Sigma_{i+1} = \Sigma_i</math>.
<math>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1})</math>.<br>
Обозначим через <math>g(x, y_1)</math> часть этой формулы без первого квантора, то есть <math>g(x, y_1) = \forall y_2 \exists y_3 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1})</math>.
Рассмотрим язык <math>L_g = \{ \langle x, y_1 \rangle | g(x, y_1) = 1\}</math>.<br>
Получим <math>L_g \in \Pi_i = \Sigma_i</math>.
<math>\exists R_2 \langle x, y_1 \rangle \in L_g \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_2(x, y_1, y_2 \ldots y_{i+1})</math>.
<math>x \in L \Leftrightarrow \exists y_1 \exists y_2 \forall y_3 \ldots Q y_{i+1} R_2(x, \overline{y_1, y_2} \ldots y_{i+1})</math>.
Значит, <math>L \in \Sigma_i</math>, что и требовалось доказать.
