Классы PH, Σ и Π — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 26 промежуточных версий 8 участников)
Строка 1: Строка 1:
==Классы <tex>\Sigma_{i}</tex> и <tex>\Pi_{i}</tex>==
+
 
 +
== Классы Σ и Π ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\Sigma_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p - poly : \forall x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\},</tex><br/>
+
<tex>\Sigma_{i} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p</tex> {{---}} <tex>poly : \forall x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\},</tex><br/>
где <tex>L</tex> - формальный язык <tex>,Q = \exists</tex> для <tex>i = 2k-1,</tex> <tex>Q = \forall</tex> для <tex>i = 2k</tex>.
+
где <tex>L</tex> формальный язык <tex>,Q = \exists</tex> для <tex>i = 2k-1,</tex> <tex>Q = \forall</tex> для <tex>i = 2k</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>\Pi_{i} = \{L|\exists R(x, y_{1},\cdots,y_{i}) \in P, p - poly : \forall x \in L \Leftrightarrow \forall y_{1} \exists y_{2} \forall y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x, y_{1}, \cdots, y_{i}) \},</tex><br/>
+
<tex>\Pi_{i} = \{L \bigm| \exists R(x, y_{1},\cdots,y_{i}) \in \mathrm{P}, p</tex> {{---}} <tex>poly : \forall x \in L \Leftrightarrow \forall y_{1} \exists y_{2} \forall y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x, y_{1}, \cdots, y_{i}) \},</tex><br/>
где <tex>L</tex> - формальный язык <tex>,Q = \forall</tex> для <tex>i = 2k - 1,</tex> <tex>Q = \exists</tex> для <tex>i = 2k</tex>.
+
где <tex>L</tex> формальный язык <tex>,Q = \forall</tex> для <tex>i = 2k-1,</tex> <tex>Q = \exists</tex> для <tex>i = 2k</tex>.
 
}}
 
}}
  
==Взаимоотношения между классами <tex>\Sigma_{i}</tex> и <tex>\Pi_{i}</tex>==
+
== Соотношения между классами Σ и Π ==
 
{{Теорема
 
{{Теорема
|statement = <tex>\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>
+
|statement = <tex>\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.
|proof = <tex>\left]L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i})\right.</tex><br/>
+
|proof = Пусть <tex>L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)</tex>.<br/>
<tex>? L \in \Sigma_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>
+
Проверим, что <tex>L \in \Sigma_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>.
 
<br/>
 
<br/>
 
   <tex>R'(x,y_{1},\cdots,y_{i+1})</tex> {
 
   <tex>R'(x,y_{1},\cdots,y_{i+1})</tex> {
     return <tex>R(x,y_{1},\cdots,y_{i})</tex>
+
     return <tex>R(x,y_{1},\cdots,y_{i})</tex>;
 
   }
 
   }
<tex>? L \in \Pi_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \forall y_{0} \exists y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>
+
Проверим, что <tex>L \in \Pi_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \forall y_{0} \exists y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>.
 
<br/>
 
<br/>
 
   <tex>R''(x,y_{0},y_{1},\cdots,y_{i})</tex> {
 
   <tex>R''(x,y_{0},y_{1},\cdots,y_{i})</tex> {
     return <tex>R(x,y_{1},\cdots,y_{i})</tex>
+
     return <tex>R(x,y_{1},\cdots,y_{i})</tex>;
 
   }
 
   }
Т.о., <tex>\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.
+
Таким образом, <tex>\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
|statement = <tex>\Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>
+
|statement = <tex>\Sigma_{i} = \mathrm{co\Pi_{i}}</tex>.
|proof = <tex>\left]L \in \Pi_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \forall y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i})\right.</tex><br/>
+
|proof = <tex>\mathrm{co\Pi_{i}} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p</tex> {{---}} <tex>poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}.</tex><br/>
<tex>? L \in \Pi_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \forall y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})</tex>
+
Из самого выражения для <tex>\mathrm{co\Pi_{i}}</tex> очевидно равенство.
<br/>
+
}}
  <tex>R'(x,y_{1},\cdots,y_{i+1})</tex> {
+
 
    return <tex>R(x,y_{1},\cdots,y_{i})</tex>
+
== Пример Σ и Π-полных задач ==
  }
+
{{Определение
<tex>? L \in \Sigma_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \exists y_{0} \forall y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})</tex>
+
|definition = Задачей <tex>\mathrm{QBF^{\Sigma}_{k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\exists</tex>.<br/>
<br/>
+
<tex>\mathrm{QBF^{\Sigma}_{k}} = \{\phi \bigm| \exists X_{1} \forall X_{2} \exists X_{3} \cdots : \phi(X_{1} \cdots X_{k})\}</tex>,<br/>
  <tex>R''(x,y_{0},y_{1},\cdots,y_{i})</tex> {
+
где <tex>X_{i}</tex> {{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.
    return <tex>R(x,y_{1},\cdots,y_{i})</tex>
 
  }
 
Т.о., <tex>\Pi_{i} \subset \Sigma_{i+1}, \Pi_{i} \subset \Pi_{i+1} \Rightarrow \Pi_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</tex>.
 
 
}}
 
}}
 +
<tex>\mathrm{QBF^{\Sigma}_{k}}</tex> {{---}} <tex>\mathrm{\Sigma_{k}}</tex>-полная задача (доказательство аналогично доказательству [[Теорема Бермана — Форчуна|coNP-полноты TAUT]]).
  
{{Теорема
+
{{Определение
|statement = <tex>\Sigma_{i} = co\Pi_{i}</tex>
+
|definition = Задачей <tex>\mathrm{QBF^{\Pi}_{k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\forall</tex>.<br/>
|proof = <tex>co\Pi_{i} = \{L|\exists R(x,y_{1},\cdots,y_{i}) \in P, p - poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}</tex><br/>
+
<tex>\mathrm{QBF^{\Pi}_{k}} = \{\phi \bigm| \forall X_{1} \exists X_{2} \forall X_{3} \cdots : \phi(X_{1} \cdots X_{k})\}</tex>,<br/>
Из самого выражения для <tex>co\Pi_{i}</tex> очевидно равенство.
+
где <tex>X_{i}</tex> {{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.
 
}}
 
}}
 +
Аналогично предыдущей, <tex>\mathrm{QBF^{\Pi}_{k}}</tex> {{---}} <tex>\mathrm{\Pi_{k}}</tex>-полная задача.
  
==Класс <tex>PH</tex>==
+
== Класс PH ==
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<tex>PH = {\bigcup \atop {k \in \mathbb{N}}} \Sigma_{i} = {\bigcup \atop {k \in \mathbb{N}}} \Pi_{i} = {\bigcup \atop {k \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})</tex>
+
<tex>\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} \Sigma_{i}</tex>.<br/>
 +
}}
 +
Замечание: иногда удобнее пользоваться альтернативными определениями <tex>\mathrm{PH}</tex>. Например:
 +
* <tex>\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} \Pi_{i}</tex>,<br/>
 +
* <tex>\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})</tex>.
 +
 
 +
{{Теорема
 +
|statement = <tex>\mathrm{PH} \subset \mathrm{PS}</tex>.
 +
|proof = Пусть <tex>L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)</tex>.<br/>
 +
То есть, для перебора всех возможных значений <tex>y_{j}</tex> потребуется не более, чем <tex>i \cdot poly(|x|)</tex> памяти. Заметим, что <tex>i \cdot poly(|x|)</tex> тоже полином.
 +
Таким образом, для любого формального языка из <tex>\mathrm{PH}</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>\mathrm{PH}</tex> принадлежит <tex>\mathrm{PS}</tex>.
 
}}
 
}}
 +
 +
[[Категория:Классы сложности]]

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

Классы Σ и Π

Определение:
[math]\Sigma_{i} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p[/math][math]poly : \forall x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \exists y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\},[/math]
где [math]L[/math] — формальный язык [math],Q = \exists[/math] для [math]i = 2k-1,[/math] [math]Q = \forall[/math] для [math]i = 2k[/math].


Определение:
[math]\Pi_{i} = \{L \bigm| \exists R(x, y_{1},\cdots,y_{i}) \in \mathrm{P}, p[/math][math]poly : \forall x \in L \Leftrightarrow \forall y_{1} \exists y_{2} \forall y_{3} \cdots Q y_{i} : \forall j |y_{j}|~\le~p(|x|), R(x, y_{1}, \cdots, y_{i}) \},[/math]
где [math]L[/math] — формальный язык [math],Q = \forall[/math] для [math]i = 2k-1,[/math] [math]Q = \exists[/math] для [math]i = 2k[/math].


Соотношения между классами Σ и Π

Теорема:
[math]\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)[/math].
Проверим, что [math]L \in \Sigma_{i+1} \Leftrightarrow \exists R' : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} \bar{Q} y_{i+1} : R'(x,y_{1},\cdots,y_{i},y_{i+1})[/math].

 [math]R'(x,y_{1},\cdots,y_{i+1})[/math] {
   return [math]R(x,y_{1},\cdots,y_{i})[/math];
 }

Проверим, что [math]L \in \Pi_{i+1} \Leftrightarrow \exists R'' : x \in L \Leftrightarrow \forall y_{0} \exists y_{1} \cdots Q y_{i} : R''(x,y_{0},y_{1},\cdots,y_{i})[/math].

 [math]R''(x,y_{0},y_{1},\cdots,y_{i})[/math] {
   return [math]R(x,y_{1},\cdots,y_{i})[/math];
 }
Таким образом, [math]\Sigma_{i} \subset \Sigma_{i+1}, \Sigma_{i} \subset \Pi_{i+1} \Rightarrow \Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}[/math].
[math]\triangleleft[/math]
Теорема:
[math]\Sigma_{i} = \mathrm{co\Pi_{i}}[/math].
Доказательство:
[math]\triangleright[/math]

[math]\mathrm{co\Pi_{i}} = \{L \bigm| \exists R(x,y_{1},\cdots,y_{i}) \in \mathrm{P}, p[/math][math]poly: x \in L \Leftrightarrow \exists y_{1} \forall y_{2} \cdots Q y_{i} : \forall j |y_j|~\le~p(|x|), R(x,y_{1},\cdots,y_{i})\}.[/math]

Из самого выражения для [math]\mathrm{co\Pi_{i}}[/math] очевидно равенство.
[math]\triangleleft[/math]

Пример Σ и Π-полных задач

Определение:
Задачей [math]\mathrm{QBF^{\Sigma}_{k}}[/math] называется объединение удовлетворимых булевых формул с [math]k[/math] изменениями кванторов, где первым квантором является [math]\exists[/math].

[math]\mathrm{QBF^{\Sigma}_{k}} = \{\phi \bigm| \exists X_{1} \forall X_{2} \exists X_{3} \cdots : \phi(X_{1} \cdots X_{k})\}[/math],

где [math]X_{i}[/math] — попарно непересекающиеся множества аргументов [math]\phi[/math].

[math]\mathrm{QBF^{\Sigma}_{k}}[/math][math]\mathrm{\Sigma_{k}}[/math]-полная задача (доказательство аналогично доказательству coNP-полноты TAUT).


Определение:
Задачей [math]\mathrm{QBF^{\Pi}_{k}}[/math] называется объединение удовлетворимых булевых формул с [math]k[/math] изменениями кванторов, где первым квантором является [math]\forall[/math].

[math]\mathrm{QBF^{\Pi}_{k}} = \{\phi \bigm| \forall X_{1} \exists X_{2} \forall X_{3} \cdots : \phi(X_{1} \cdots X_{k})\}[/math],

где [math]X_{i}[/math] — попарно непересекающиеся множества аргументов [math]\phi[/math].

Аналогично предыдущей, [math]\mathrm{QBF^{\Pi}_{k}}[/math][math]\mathrm{\Pi_{k}}[/math]-полная задача.

Класс PH

Определение:
[math]\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} \Sigma_{i}[/math].

Замечание: иногда удобнее пользоваться альтернативными определениями [math]\mathrm{PH}[/math]. Например:

  • [math]\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} \Pi_{i}[/math],
  • [math]\mathrm{PH} = {\bigcup \atop {i \in \mathbb{N}}} (\Sigma_{i} \cup \Pi_{i})[/math].
Теорема:
[math]\mathrm{PH} \subset \mathrm{PS}[/math].
Доказательство:
[math]\triangleright[/math]

Пусть [math]L \in \Sigma_{i} \Rightarrow \exists R : x \in L \Leftrightarrow \exists y_{1} \cdots Q y_{i} : R(x,y_{1},\cdots,y_{i}), \forall j |y_{j}| \le poly(|x|)[/math].
То есть, для перебора всех возможных значений [math]y_{j}[/math] потребуется не более, чем [math]i \cdot poly(|x|)[/math] памяти. Заметим, что [math]i \cdot poly(|x|)[/math] тоже полином.

Таким образом, для любого формального языка из [math]\mathrm{PH}[/math] существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из [math]\mathrm{PH}[/math] принадлежит [math]\mathrm{PS}[/math].
[math]\triangleleft[/math]