Классы PH, Σ и Π — различия между версиями
м (→Классы Σ и Π: dollar signs removed.... what were they doing here in the first place?) |
м (rollbackEdits.php mass rollback) |
(не показана 1 промежуточная версия 1 участника) | |
(нет различий)
|
Текущая версия на 19:19, 4 сентября 2022
Классы Σ и Π
Определение: |
где — формальный язык для для . | —
Определение: |
где — формальный язык для для . | —
Соотношения между классами Σ и Π
Теорема: |
. |
Доказательство: |
Пусть { return ; } Проверим, что Таким образом, { return ; } . |
Теорема: |
. |
Доказательство: |
|
Пример Σ и Π-полных задач
Определение: |
Задачей
| называется объединение удовлетворимых булевых формул с изменениями кванторов, где первым квантором является .
Определение: |
Задачей
| называется объединение удовлетворимых булевых формул с изменениями кванторов, где первым квантором является .
Аналогично предыдущей,
— -полная задача.Класс PH
Определение: |
Замечание: иногда удобнее пользоваться альтернативными определениями
. Например:-
- .
Теорема: |
. |
Доказательство: |
Пусть |