Введение

В теории вычислительной сложности класс сложности ⊕P (произносится как "паритет P") — это класс задач принятия, разрешимых недетерминированной машиной Тьюринга за полиномиальное время, где условием принятия является нечётное количество принимающих вычислительных путей. Примером задачи ⊕P является вопрос: "имеет ли данный граф нечётное число совершенных паросочетаний?". Класс был определён Пападимитриу и Захосом в 1983 году. Примером ⊕P-полной задачи (при использовании многих одномерных сведений) является ⊕SAT: при данной булевой формуле, нечётное ли количество её удовлетворяющих назначений? Это следует из теоремы Кука — Левина, поскольку сведения являются экономными. ⊕P является классом подсчёта и может рассматриваться как нахождение младшего значащего бита ответа на соответствующую #P-задачу. Задача нахождения старшего значащего бита находится в классе PP. Считается, что PP — значительно более сложный класс, чем ⊕P; например, существует релятивизированная вселенная (см. оракульная машина), где P = ⊕P ≠ NP = PP = EXPTIME, как показали Бейгель, Бурман и Фортноу в 1998 году. В то время как теорема Тоды показывает, что PPP содержит PH, ⊕P не известно даже содержит NP. Однако первая часть доказательства теоремы Тоды показывает, что BPP⊕P содержит PH. Лэнс Фортноу написал краткое доказательство этой теоремы. ⊕P содержит задачу об автоморфизме графа, и, более того, эта задача является низшей для ⊕P. Он также тривиально содержит UP, поскольку все задачи в UP имеют либо ноль, либо один принимающий путь. В более общем смысле, ⊕P является низким для себя, что означает, что такая машина не получает никакой дополнительной мощности от возможности мгновенно решать любую задачу ⊕P. Символ ⊕ в названии класса может быть отсылкой к использованию символа ⊕ в булевой алгебре для обозначения оператора исключающего ИЛИ. Это имеет смысл, потому что если рассматривать "принимает" как 1, а "не принимает" как 0, то результат работы машины является исключающим ИЛИ результатов каждого вычислительного пути.