Классы Σ и Π
| Определение: |
[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]-полная задача (доказательство аналогично доказательству полноты TQBF).
| Определение: |
Задачей [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] |
