Изменения

{{Лемма|statement == Утверждение теоремы ==Если <mathtex>\Sigma_i = \Sigma_{i+1}</mathtex>, то <mathtex>\Pi_i = \Pi_{i+1}</tex>.|proof = <tex>L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i = PH\Leftrightarrow L \in \Pi_i</mathtex>.}}

== Доказательство Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> =={{Теорема|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_j</tex>.<br/>Докажем по индукции.<br/>Из '''База'''. <mathtex>\Sigma_i = \Sigma_{i+1}</mathtex> из условия.<br/>'''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_{n+1} = \Sigma_{n+2}</tex>.<br/>Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>. <tex>L = \{x \bigm| \exists y_1 \forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим <tex> очевидным образом следует \forall y_2 \ldots Q y_{n+2} R_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>.Тогда получим язык <mathtex>L_f = \{\Pi_i langle x, y_1\rangle \bigm| f(x, y_1) = 1\}</tex>.<br/>Заметим, что <tex>L_f \in \Pi_{in+1}</tex> и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>.<br/>Из определения сложностного класса <tex>\Pi_n</tex> получаем, что <tex>\exists 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_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. Следовательно, <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>. <tex>R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex> '''return''' <tex>R_{L_f}^n(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>То есть язык <tex>L \in \Sigma_{n+1}</mathtex>.}}

Докажем== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> =={{Теорема|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, что если то <mathtex>\Sigma_i = \Sigma_mathrm{i+1PH}</mathtex>.|proof = Для доказательства покажем, то что <mathtex>\Sigma_i = \Sigma_{i+21}</mathtex>, и воспользуемся предыдущей теоремой.

Рассмотрим язык <mathtex>L \in \Sigma_{i+21}</mathtex>.<br>Если <mathtex>L =\{x \in L </math>, значит, <math>bigm| \exists y_1 \forall y_2 \ldots Q y_{ni+21} R_L^{i+1} R(x, y_1 \ldots y_{ni+21})\}</mathtex>. Обозначим часть формулы (исключая <math>\exists y_1</math>) <mathtex>\forall y_2 \exists y_3 \ldots Q y_{ni+21} R_L^{i+1} R(x, y_1 \ldots y_{ni+21}) = f(x, y_1)</mathtex>. Тогда формула преобразуется в Получим язык <mathtex>L_f = \exists { \langle x, y_1 \rangle \bigm| f(x, y_1)= 1\}</mathtex>.<br>Тогда получим <mathtex>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 L_f \Leftrightarrow \exists y_1 y_2 \forall y_3 \colon 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_f = 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 \colon fldots, 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 = 1\mathrm{P}</mathtex>, а потому формулировка теоремы не имеет смысла при <tex>i = 0</tex>.

Значит== Литература ==* S.Arora, B.Barak. The polynomial hierarchy and alternations. Cambridge University, <math>L_f \in \Pi_{n+1}<January 2007. [http:/math>/www.<br>Тогда раз <math>\Sigma_i = \Sigma_{i+1}<cs.princeton.edu/math>, то <math>\Pi_i = \Pi_{i+1}<theory/math>, то <math>L_f \in \Pi_n<complexity/math>phchap.pdf]

<math>\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})</math>, где переменные <math>x</math> и <math>y_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 \Sigma_n</math>, что и требовалось доказать.[[Категория: Теория сложности]]