Паритет П

Оглавление1 Четность P1.1 Определение класса сложности ⊕P1.2 ⊕P-полные задачи1.3 Связь с другими классами сложности1.4 Примеры задач в ⊕P1.5 Символика ⊕P2 […]

Четность P

  • Определение класса сложности ⊕P

    • ⊕P – класс задач, решаемых недетерминированными машинами Тьюринга за полиномиальное время с нечетным числом принимающих путей. 
    • Пример задачи ⊕P: проверка наличия нечетного числа идеальных соответствий в графе. 
  • ⊕P-полные задачи

    • ⊕SAT – задача определения нечетного числа удовлетворяющих назначений в логической формуле. 
    • Теорема Кука-Левина показывает, что ⊕SAT является ⊕P-полной задачей. 
  • Связь с другими классами сложности

    • ⊕P рассматривается как поиск наименее значимого бита в задачах класса #P. 
    • Проблема поиска наиболее значимого бита (PP) считается более сложной, чем ⊕P. 
    • Теорема Тоды показывает, что класс PPP содержит класс PH, но не содержит NP. 
  • Примеры задач в ⊕P

    • Проблема автоморфизма графа является небольшой задачей для ⊕P. 
    • Все задачи в UP имеют либо 0, либо 1 принимающий путь, что делает их тривиально в ⊕P. 
  • Символика ⊕P

    • Символ ⊕ может быть связан с оператором исключающей дизъюнкции в булевой алгебре. 
    • Если “принимает” равно 1, а “не принимает” равно 0, то результат работы машины будет равен исключающему разделению результатов каждого пути вычисления. 

Полный текст статьи:

Паритет П — Википедия

Оставьте комментарий

Прокрутить вверх