81
правка
Изменения
м
→Классы Σ и Π: dollar signs removed.... what were they doing here in the first place?
== Классы Σ и Π ==
{{Определение
|definition =
<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>.}} {{Определение|definition =<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 \exists forall y_{1} \forall exists y_{2} \exists 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 = \existsforall</tex> для <tex>i = 2k - 1,</tex> <tex>Q = \forallexists</tex> для <tex>i = 2k</tex>.}} == Соотношения между классами Σ и Π =={{Теорема|statement = <tex>\Sigma_{i} \subset \Sigma_{i+1} \cap \Pi_{i+1}</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>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/> <tex>R'(x,y_{1},\cdots,y_{i+1})</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>.<br/> <tex>R''(x,y_{0},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>.}} {{Теорема|statement = <tex>\Sigma_{i} = \mathrm{co\Pi_{i}}</tex>.|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>\mathrm{co\Pi_{i}}</tex> очевидно равенство.
}}
== Пример Σ и Π-полных задач ==
{{Определение
|definition = Задачей <tex>\mathrm{QBF^{\Sigma}_{k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\exists</tex>.<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>X_{i}</tex> {{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.
}}
<tex>\mathrm{QBF^{\Sigma}_{k}}</tex> {{---}} <tex>\mathrm{\Sigma_{k}}</tex>-полная задача (доказательство аналогично доказательству [[Теорема Бермана — Форчуна|coNP-полноты TAUT]]).
{{Определение
|definition = Задачей <tex>\mathrm{QBF^{\Pi}_{k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\forall</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>X_{i}</tex> {{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.
}}
Аналогично предыдущей, <tex>\mathrm{QBF^{\Pi}_{k}}</tex> {{---}} <tex>\mathrm{\Pi_{k}}</tex>-полная задача.
== Класс PH ==
{{Определение
|definition =
<tex>\Pi_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 {L|i \in \exists Rmathbb{N}}} (x, y_\Sigma_{1i},\cdots,y_cup \Pi_{i}) </tex>. {{Теорема|statement = <tex>\mathrm{PH} \subset \mathrm{PS}</tex>.|proof = Пусть <tex>L \in P, p - poly \Sigma_{i} \Rightarrow \exists R : \forall x \in L \Leftrightarrow \forall exists y_{1} \exists cdots Q y_{2i} \forall : R(x,y_{31} ,\cdots Q ,y_{i} ), \forall j |y_{j}| \le poly(|x|)</tex>.<br/>То есть,для перебора всех возможных значений <tex>y_{j}</tex> где потребуется не более, чем <tex>Li \cdot poly(|x|)</tex> - формальный язык памяти. Заметим, что <tex>,Q = i \forallcdot poly(|x|)</tex> тоже полином.Таким образом, для любого формального языка из <tex>i = 2k - 1,\mathrm{PH}</tex> существует программа, разрешающая его на полиномиальной памяти. То есть, любой формальный язык из <tex>Q = \existsmathrm{PH}</tex> для принадлежит <tex>i = 2k\mathrm{PS}</tex>.
}}
[[Категория:Классы сложности]]
