108
правок
Изменения
Нет описания правки
== Пример Σ-полной задачи ==
{{Определение
|statement 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>.
{{Определение
|statement 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>.
