108
правок
Изменения
Нет описания правки
Из самого выражения для <tex>\mathrm{co\Pi_{i}}</tex> очевидно равенство.
}}
== Пример Σ-полной задачи ==
{{Определение
|statement = Задачей <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_{k}}</tex> {{---}} <tex>\mathrm{\Sigma_{k}}</tex>-полная задача (доказательство аналогично доказательству [[PS-полнота языка верных булевых формул с кванторами (TQBF)|полноты TQBF]].
{{Определение
|statement = Задачей <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 ==
