Паритет П
В теории сложности вычислений класс сложности ⊕ P (произносится как «четность P») — это класс задач решения , решаемых недетерминированной машиной Тьюринга за полиномиальное время, где условием приемлемости является то, что количество принимающих путей вычислений нечетно. Пример задачи ⊕ P : «Имеет ли данный граф нечетное количество идеальных паросочетаний ?» Класс был определен Пападимитриу и Захосом в 1983 году. [1]
Примером ⊕ P -полной задачи (при редукции «многие единицы ») является ⊕SAT: для данной булевой формулы является ли число удовлетворяющих ее присваиваний нечетным? Это следует из теоремы Кука – Левина, поскольку сокращение является экономным . [2]
⊕ P — это счетный класс, и его можно рассматривать как поиск младшего бита ответа на соответствующую задачу #P . Проблема поиска старшего бита находится в PP . PP Считается, что — значительно более сложный класс, чем ⊕ P ; например, существует релятивизированная вселенная (см. оракул-машина ), где P = ⊕ P ≠ NP = PP = EXPTIME , как показали Бейгель, Бурман и Фортноу в 1998 году. [3]
Хотя теорема Тоды показывает, что P ПП содержит PH , P ⊕ P неизвестно, что он даже содержит NP . Однако первая часть доказательства теоремы Тоды показывает, что BPP ⊕ P содержит РН . Лэнс Фортноу написал краткое доказательство этой теоремы. [4]
⊕ P содержит проблему автоморфизма графа , и на самом деле эта проблема является низкой для P. ⊕ [5] Он также тривиально содержит UP , поскольку все задачи в UP имеют либо ноль, либо один принимающий путь. В более общем смысле, ⊕ P , само по себе мало а это означает, что такая машина не получает никакой мощности от возможности ⊕ P. мгновенного решения любой проблемы
Символ ⊕ в названии класса может быть ссылкой на использование символа ⊕ в булевой алгебре для обозначения оператора исключительной дизъюнкции . Это имеет смысл, поскольку если мы считаем, что «принимает» равное 1, а «не принимает» равное 0, результатом работы машины является исключительное дизъюнкция результатов каждого пути вычислений.
Внешние ссылки [ править ]
Ссылки [ править ]
- ^ CH Пападимитриу и С. Захос . Два замечания о силе счета . В материалах 6-й конференции GI по теоретической информатике , Конспекты лекций по информатике , том 145, Springer-Verlag, стр. 269–276. 1983.
- ^ Абхишек Шетти, Рагхав Малхотра иЧандан Саха. 26-й лекции Конспекты по теории сложности вычислений , 2015 г.
- ^ Р. Бейгель, Х. Бурман и Л. Фортноу . NP может быть не таким простым, как поиск уникальных решений. В материалах ACM STOC'98 , стр. 203–208. 1998.
- ^ Фортнау, Лэнс (2009), «Простое доказательство теоремы Тоды», Theory of Computing , 5 : 135–140, doi : 10.4086/toc.2009.v005a007
- ^ Кёблер, Йоханнес; Шенинг, Уве; Торан, Хакобо (1992), «Изоморфизм графов низкий для PP», Computational Complexity , 2 (4): 301–330, doi : 10.1007/BF01200427 .