108
правок
Изменения
Нет описания правки
}}
== Пример Σи Π-полной задачи полных задач ==
{{Определение
|definition = Задачей <tex>\mathrm{QBF^{\Sigma}_{k}}</tex> называется объединение удовлетворимых булевых формул с <tex>k</tex> изменениями кванторов, где первым квантором является <tex>\exists</tex>.<br/>
где <tex>X_{i}</tex> {{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.
}}
<tex>\mathrm{QBF_QBF^{\Sigma}_{k}}</tex> {{---}} <tex>\mathrm{\Sigma_{k}}</tex>-полная задача (доказательство аналогично доказательству [[PS-полнота языка верных булевых формул с кванторами (TQBF)|полноты TQBF]].
{{Определение
где <tex>X_{i}</tex> {{---}} попарно непересекающиеся множества аргументов <tex>\phi</tex>.
}}
Аналогично предыдущей, <tex>\mathrm{QBF^{\Pi}_{k}}</tex> {{---}} <tex>\mathrm{\Pi_{k}}</tex>-полная задача.
== Класс PH ==
