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 \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>\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 ==
}}
[[Категория: Теория Классы сложности]]
