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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 5 участников)
Строка 1: Строка 1:
 
{{Лемма
 
{{Лемма
 
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.
 
|statement = Если <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>.
|proof = Так как <tex>\Sigma_i = \Sigma_{i+1}</tex>, то любой язык <tex>L \in \Sigma_{i+1}</tex> входит в сложностный класс <tex>\Sigma_i</tex>. Очевидно, что если язык <tex>L \in \Sigma_i</tex>, то <tex>\overline{L} \in \Pi_i</tex>.<br/> Тогда для языка <tex>L</tex> выполнено <tex>\overline{L} \in \Pi_{i+1} \Leftrightarrow L \in \Sigma_{i+1} \Leftrightarrow L \in \Sigma_i \Leftrightarrow \overline{L} \in \Pi_i</tex>
+
|proof = <tex>L \in \Pi_{i+1} \Leftrightarrow \overline{L} \in \Sigma_{i+1} \Leftrightarrow \overline{L} \in \Sigma_i \Leftrightarrow L \in \Pi_i</tex>.
 
}}
 
}}
  
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Sigma_{i+1}</math> ==
+
== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Sigma_{i+1}</tex> ==
 
 
 
{{Теорема
 
{{Теорема
|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 = \mathrm{PH}</tex>.
|proof = Из <tex>\Sigma_i = \Sigma_{i+1}</tex> очевидным образом следует <tex>\Pi_i = \Pi_{i+1}</tex>.
+
|proof = Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_j</tex>.<br/>
 
+
Докажем по индукции.<br/>
Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_n = \Sigma_{n+2}</tex>.
+
'''База'''. <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>.<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>x \in L </tex>, значит, <tex>\exists y_1 \forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2})</tex>. Обозначим часть формулы (исключая <tex>\exists y_1</tex>) <tex>\forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>. Тогда формула преобразуется в <tex>\exists y_1 f(x, y_1)</tex>.<br>
+
Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \bigm| f(x, y_1) = 1\}</tex>.<br/>
Тогда получим <tex>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\}</tex>.
+
Заметим, что <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>L_f \in \Pi_{n+1}</tex>.<br>
+
<tex>R_L^{n+1}(x, y_1, y_2 \ldots y_{n+1})</tex>
Тогда раз <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>, то <tex>L_f \in \Pi_n</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>\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})</tex>, где переменные <tex>x</tex> и <tex>y_1</tex> представляют собой одну переменную.
 
 
 
Получается, что <tex>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})</tex>, откуда следует <tex>L \in \Sigma_{n+2} \Rightarrow L \in \Sigma_{n+1}</tex>, что и требовалось доказать.
 
 
}}
 
}}
  
== Теорема о коллапсе полиномиальной иерархии при совпадении <math>\Sigma_i</math> и <math>\Pi_i</math> ==
+
== Теорема о коллапсе полиномиальной иерархии при совпадении <tex>\Sigma_i</tex> и <tex>\Pi_i</tex> ==
 
{{Теорема
 
{{Теорема
|statement = Если <tex>\Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = PH</tex>.
+
|statement = Если существует <tex>i > 0\colon \Sigma_i = \Pi_i</tex>, то <tex>\Sigma_i = \mathrm{PH}</tex>.
 
|proof =  
 
|proof =  
Доказательство аналогично доказательству предыдущей теоремы. Мы снова будем удалять квантор из формулы и получим, что если можно удалить один квантор, то можно удалить их все.
+
Для доказательства покажем, что <tex>\Sigma_i = \Sigma_{i+1}</tex>, и воспользуемся предыдущей теоремой.
  
Докажем, что <tex>\Sigma_{i+1} = \Sigma_i</tex>.
+
Рассмотрим язык <tex>L \in \Sigma_{i+1}</tex>. <tex>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})\}</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 \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>.
 +
}}
 +
Заметим, что <tex>\Sigma_0 = \Pi_0 = \mathrm{P}</tex>, а потому формулировка теоремы не имеет смысла при <tex>i = 0</tex>.
  
<tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1})</tex>.<br>
+
== Литература ==
Обозначим через <tex>g(x, y_1)</tex> часть этой формулы без первого квантора, то есть <tex>g(x, y_1) = \forall y_2 \exists y_3 \ldots Q y_{i+1} R(x, y_1 \ldots y_{i+1})</tex>.
+
* S.Arora, B.Barak. The polynomial hierarchy and alternations. Cambridge University, January 2007. [http://www.cs.princeton.edu/theory/complexity/phchap.pdf]
  
Рассмотрим язык <tex>L_g = \{ \langle x, y_1 \rangle | g(x, y_1) = 1\}</tex>.<br>
+
[[Категория: Теория сложности]]
Получим <tex>L_g \in \Pi_i = \Sigma_i</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 \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>, что и требовалось доказать.
 
}}
 

Текущая версия на 19:28, 4 сентября 2022

Лемма:
Если [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]