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