Изменения

|proof = Так как <tex>\Sigma_i = \Sigma_{i+1}</tex>, то любой язык <tex>L \in \Sigma_Pi_{i+1}</tex> входит в сложностный класс <tex>\Sigma_i</tex>. Очевидно, что если язык <tex>L \in \Sigma_i</tex>, то <tex>Leftrightarrow \overline{L} \in \Pi_i</tex>.<br/> Тогда для языка <tex>L</tex> выполнено <tex>\overline{L} \in \Pi_Sigma_{i+1} \Leftrightarrow L \in \Sigma_overline{i+1L} \Leftrightarrow L \in \Sigma_i \Leftrightarrow \overline{L} \in \Pi_i</tex>.

== Теорема о коллапсе полиномиальной иерархии при совпадении <mathtex>\Sigma_i</mathtex> и <mathtex>\Sigma_{i+1}</mathtex> == 

|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.|proof = Из Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_{i+1}Sigma_j</tex> очевидным образом следует .<br/>Докажем по индукции.<br/>'''База'''. <tex>\Pi_i Sigma_i = \Pi_Sigma_{i+1}</tex>из условия.<br/> '''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_n Sigma_{n+1} = \Sigma_{n+2}</tex>.<br/>Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>.<br>Если <tex>L = \{x \in L </tex>, значит, <tex>bigm| \exists y_1 \forall y_2 \ldots Q y_{n+2} RR_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим часть формулы (исключая <tex>\exists y_1</tex>) <tex>\forall y_2 \ldots Q y_{n+2} RR_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>. Тогда формула преобразуется в <tex>\exists y_1 f(x, y_1)</tex>.<br>Тогда получим язык <tex>x \in L \Leftrightarrow \exists y_1 \colon \langle x, y_1\rangle \in L_f = \{\langle x, y_1\rangle \colon bigm| f(x, y_1) = 1\}</tex>.<br/> ЗначитЗаметим, что <tex>L_f \in \Pi_{n+1}</tex>.<br>Тогда раз и из вышедоказанной леммы следует, что <tex>L_f \Sigma_i = in \Sigma_{i+1}Pi_n</tex>, то <tex>\Pi_i = \Pi_{i+1}.<br/tex>, то Из определения сложностного класса <tex>L_f \in \Pi_n</tex> получаем, что <tex>\exists R_1 R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_1R_{L_f}^{n}(\overline{langle x, y_1}\rangle, y_2 \ldots y_{n+1})</tex>, где переменные <tex>x</tex> и <tex>y_1</tex> представляют собой одну переменную. ПолучаетсяСледовательно, что <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_1R_L^{n+1}(x, y_1, y_2 \overlineldots y_{n+1})</tex>. <tex>R_L^{n+1}(x, y_1}, y_2 \ldots y_{n+1})</tex>, откуда следует '''return''' <tex>L R_{L_f}^n(\langle x, y_1\in rangle, y_2 \Sigma_ldots y_{n+21} \Rightarrow )</tex>То есть язык <tex>L \in \Sigma_{n+1}</tex>, что и требовалось доказать.

== Теорема о коллапсе полиномиальной иерархии при совпадении <mathtex>\Sigma_i</mathtex> и <mathtex>\Pi_i</mathtex> ==

|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.

Доказательство аналогично доказательству предыдущей теоремы. Мы снова будем удалять квантор из формулы и получимДля доказательства покажем, что если можно удалить один квантор<tex>\Sigma_i = \Sigma_{i+1}</tex>, то можно удалить их всеи воспользуемся предыдущей теоремой.

ДокажемРассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>L =\{x \bigm| \exists y_1 \forall y_2 \ldots Q y_{i+1} R_L^{i+1}(x, что y_1 \ldots y_{i+1})\}</tex>. Обозначим <tex>\Sigma_forall y_2 \exists y_3 \ldots Q y_{i+1} R_L^{i+1}(x, y_1 \ldots y_{i+1} ) = f(x, y_1)</tex>. Получим язык <tex>L_f = \{ \langle x, y_1 \rangle \bigm| f(x, y_1) = 1\}</tex>.<br>Тогда <tex>L_f \in \Pi_i</tex>, и из условия теоремы <tex>L_f \in \Sigma_i</tex>.<br/>По определению сложностного класса <tex>\Sigma_i\; \exists R_{L_f}^i \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \exists y_2 \forall y_3 \ldots Q y_{i+1} R_{L_f}^i(\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_L^i(x, \langle y_1, y_2\rangle \ldots y_{i+1})</tex>. <br/> <tex>R_L^i(x, \langle y_1, y_2\rangle, y_3 \ldots, y_{i+1})</tex> '''return''' <tex>R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3 \ldots y_{i+1})</tex>Значит, <tex>L \in \Sigma_i</tex>.}}Заметим, что <tex>\Sigma_0 = \Pi_0 = \mathrm{P}</tex>, а потому формулировка теоремы не имеет смысла при <tex>i = 0</tex>.

<tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{i+1} R(x== Литература ==* S.Arora, y_1 \ldots y_{i+1})<B.Barak. The polynomial hierarchy and alternations. Cambridge University, January 2007. [http:/tex>/www.<br>Обозначим через <tex>g(x, y_1)<cs.princeton.edu/theory/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})<complexity/tex>phchap.pdf]

Рассмотрим язык <tex>L_g = \{ \langle x, y_1 \rangle | g(x, y_1) = 1\}</tex>.<br>Получим <tex>L_g \in \Pi_i = \Sigma_i</tex>. <tex>\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})</tex>. <tex>x \in L \Leftrightarrow \exists \langle y_1, y_2 \rangle \forall y_3 \ldots Q y_{i+1} R_2(x, \overline{y_1, y_2} \ldots y_{i+1})</tex>. Значит, <tex>L \in \Sigma_i</tex>, что и требовалось доказать.}}[[Категория: Теория сложности]]