205
правок
Изменения
м
Нет описания правки
== Теорема о коллапсе полиномиальной иерархии при совпадении <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/>
'''База'''. <tex>\Sigma_i = \Sigma_{i+1}</tex> из условия.<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>.Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \bigm| f(x, y_1) = 1\}</tex>.<br/>
Заметим, что <tex>L_f \in \Pi_{n+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}</tex>.
}}
== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==
{{Теорема
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
|proof =
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.
Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>L =\{x \colon 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>\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 \colon 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>.<br/>Заметим, что при <tex>i = 0</tex> теорема, скорее всего, неверна. Так как если взять язык <tex>L \in \Sigma_1</tex> и выполнить все шаги доказательства, то на выходе получится язык из <tex>\Sigma_1</tex>, а не из <tex>\Sigma_0</tex>.
}}
Заметим, что <tex>\Sigma_0 = \Pi_0 = \mathrm{P}</tex>, а потому формулировка теоремы не имеет смысла при <tex>i = 0</tex>.
== См. также Литература ==*S.Arora, B.Barak. The polynomial hierarchy and alternations. Cambridge University, January 2007. [http://www.cs.princeton.edu/theory/complexity/phchap.pdf] [[Классы PH, Σ и ΠКатегория: Теория сложности]]
