Теоремы о коллапсе полиномиальной иерархии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Sigma_{i+1})
м (Теорема о коллапсе полиномиальной иерархии при совпадении \Sigma_i и \Sigma_{i+1})
Строка 6: Строка 6:
 
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Sigma_{i+1}</math> ==
 
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Sigma_{i+1}</math> ==
 
{{Теорема
 
{{Теорема
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = PH</tex>.
+
|statement = Если существует <tex>i \colon \Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Sigma_i = PH</tex>.
 
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>.<br/>
 
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>.<br/>
 
Докажем по индукции.<br/>
 
Докажем по индукции.<br/>

Версия 15:43, 11 апреля 2012

Лемма:
Если [math]\Sigma_i = \Sigma_{i+1}[/math], то [math]\Pi_i = \Pi_{i+1}[/math].
Доказательство:
[math]\triangleright[/math]
Так как [math]\Sigma_i = \Sigma_{i+1}[/math], то любой язык [math]L \in \Sigma_{i+1}[/math] входит в сложностный класс [math]\Sigma_i[/math]. Очевидно, что если язык [math]L \in \Sigma_i[/math], то [math]\overline{L} \in \Pi_i[/math].
Тогда для языка [math]L[/math] выполнено [math]\overline{L} \in \Pi_{i+1} \Leftrightarrow L \in \Sigma_{i+1} \Leftrightarrow L \in \Sigma_i \Leftrightarrow \overline{L} \in \Pi_i[/math]. То есть [math]\Pi_i = \Pi_{i+1}[/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 = 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 = \Sigma_{n+2}[/math].
Рассмотрим язык [math]L \in \Sigma_{n+2}[/math]. По определению сложностного класса [math]\Sigma_{n+2}[/math] слово [math]x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2})[/math]. Обозначим [math]\forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2}) = 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]L_f \in \Pi_n[/math].

Из определения сложностного класса [math]\Pi_n\;\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(\langle x, y_1\rangle, 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(\langle x, y_1\rangle, y_2 \ldots y_{n+1})[/math]. То есть язык [math]L \in \Sigma_{n+1}[/math]. Отсюда следует, что [math]\Sigma_{n+1} = \Sigma_{n+2}[/math].
[math]\triangleleft[/math]

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

Теорема:
Если [math]\Sigma_i = \Pi_i[/math], то [math]\Sigma_i = PH[/math].
Доказательство:
[math]\triangleright[/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], что и требовалось доказать.
[math]\triangleleft[/math]