Четность P
-
Определение класса сложности ⊕P
- ⊕P — класс задач, решаемых недетерминированными машинами Тьюринга за полиномиальное время с нечетным числом принимающих путей.
- Пример задачи ⊕P: проверка наличия нечетного числа идеальных соответствий в графе.
-
⊕P-полные задачи
- ⊕SAT — задача определения нечетного числа удовлетворяющих назначений в логической формуле.
- Теорема Кука-Левина показывает, что ⊕SAT является ⊕P-полной задачей.
-
Связь с другими классами сложности
- ⊕P рассматривается как поиск наименее значимого бита в задачах класса #P.
- Проблема поиска наиболее значимого бита (PP) считается более сложной, чем ⊕P.
- Теорема Тоды показывает, что класс PPP содержит класс PH, но не содержит NP.
-
Примеры задач в ⊕P
- Проблема автоморфизма графа является небольшой задачей для ⊕P.
- Все задачи в UP имеют либо 0, либо 1 принимающий путь, что делает их тривиально в ⊕P.
-
Символика ⊕P
- Символ ⊕ может быть связан с оператором исключающей дизъюнкции в булевой алгебре.
- Если «принимает» равно 1, а «не принимает» равно 0, то результат работы машины будет равен исключающему разделению результатов каждого пути вычисления.
Полный текст статьи: