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