|
|
| Строка 38: |
Строка 38: |
| | <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>\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 y_1 \exists y_2 \forall y_3 \ldots Q y_{i+1} R_2(x, \overline{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>, что и требовалось доказать. | | Значит, <tex>L \in \Sigma_i</tex>, что и требовалось доказать. |
Теорема о коллапсе полиномиальной иерархии при совпадении [math]\Sigma_i[/math] и [math]\Sigma_{i+1}[/math]
Утверждение теоремы
Если [math]\Sigma_i = \Sigma_{i+1}[/math], то [math]\Sigma_i = PH[/math].
Доказательство
Из [math]\Sigma_i = \Sigma_{i+1}[/math] очевидным образом следует [math]\Pi_i = \Pi_{i+1}[/math].
Докажем, что если [math]\Sigma_n = \Sigma_{n+1}[/math], то [math]\Sigma_n = \Sigma_{n+2}[/math].
Рассмотрим язык [math]L \in \Sigma_{n+2}[/math].
Если [math]x \in L [/math], значит, [math]\exists y_1 \forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2})[/math]. Обозначим часть формулы (исключая [math]\exists y_1[/math]) [math]\forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2}) = f(x, y_1)[/math]. Тогда формула преобразуется в [math]\exists y_1 f(x, y_1)[/math].
Тогда получим [math]x \in L \Leftrightarrow \exists y_1 \colon \langle x, y_1\rangle \in L_f = \{\langle x, y_1\rangle \colon f(x, y_1) = 1\}[/math].
Значит, [math]L_f \in \Pi_{n+1}[/math].
Тогда раз [math]\Sigma_i = \Sigma_{i+1}[/math], то [math]\Pi_i = \Pi_{i+1}[/math], то [math]L_f \in \Pi_n[/math]
[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+2} \Rightarrow L \in \Sigma_{n+1}[/math], что и требовалось доказать.
Теорема о коллапсе полиномиальной иерархии при совпадении [math]\Sigma_i[/math] и [math]\Pi_i[/math]
Утверждение теоремы
Если [math]\Sigma_i = \Pi_i[/math], то [math]\Sigma_i = PH[/math].
Доказательство
Доказательство аналогично доказательству предыдущей теоремы. Мы снова будем удалять квантор из формулы и получим, что если можно удалить один квантор, то можно удалить их все.
Докажем, что [math]\Sigma_{i+1} = \Sigma_i[/math].
[math]x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1})[/math].
Обозначим через [math]g(x, y_1)[/math] часть этой формулы без первого квантора, то есть [math]g(x, y_1) = \forall y_2 \exists y_3 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1})[/math].
Рассмотрим язык [math]L_g = \{ \langle x, y_1 \rangle | g(x, y_1) = 1\}[/math].
Получим [math]L_g \in \Pi_i = \Sigma_i[/math].
[math]\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})[/math].
[math]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})[/math].
Значит, [math]L \in \Sigma_i[/math], что и требовалось доказать.
