Теоремы о коллапсе полиномиальной иерархии

Лемма:

Если [math]\Sigma_i = \Sigma_{i+1}[/math], то [math]\Pi_i = \Pi_{i+1}[/math].

Доказательство:

[math]\triangleright[/math]

[math]L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i \Leftrightarrow L \in \Pi_i[/math].

[math]\triangleleft[/math]

Теорема о коллапсе полиномиальной иерархии при совпадении [math]\Sigma_i[/math] и [math]\Sigma_{i+1}[/math]

Теорема:

Если существует [math]i \colon \Sigma_i = \Sigma_{i+1}[/math], то [math]\Sigma_i = \mathrm{PH}[/math].

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Теорема о коллапсе полиномиальной иерархии при совпадении [math]\Sigma_i[/math] и [math]\Pi_i[/math]

Теорема:

Если существует [math]i \gt 0\colon \Sigma_i = \Pi_i[/math], то [math]\Sigma_i = \mathrm{PH}[/math].

Доказательство:

[math]\triangleright[/math]

Для доказательства покажем, что [math]\Sigma_i = \Sigma_{i+1}[/math], и воспользуемся предыдущей теоремой. Рассмотрим язык [math]L \in \Sigma_{i+1}[/math]. [math]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})\}[/math]. Обозначим [math]\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)[/math]. Получим язык [math]L_f = \{ \langle x, y_1 \rangle \bigm| f(x, y_1) = 1\}[/math]. Тогда [math]L_f \in \Pi_i[/math], и из условия теоремы [math]L_f \in \Sigma_i[/math]. По определению сложностного класса [math]\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})[/math]. Тогда [math]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})[/math]. [math]R_L^i(x, \langle y_1, y_2\rangle, y_3 \ldots, y_{i+1})[/math] return [math]R_{L_f}^i(\langle x, y_1\rangle, y_2, y_3 \ldots y_{i+1})[/math] Значит, [math]L \in \Sigma_i[/math].

[math]\triangleleft[/math]

Заметим, что [math]\Sigma_0 = \Pi_0 = \mathrm{P}[/math], а потому формулировка теоремы не имеет смысла при [math]i = 0[/math].

Литература

• S.Arora, B.Barak. The polynomial hierarchy and alternations. Cambridge University, January 2007. [1]