Parity P

In computational complexity theory, the complexity class ⊕P (pronounced "parity P") is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. An example of a ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983.

An example of a ⊕P-complete problem (under polynomial-time many-one reductions) is ⊕SAT: given a Boolean formula, is the number of its satisfying assignments odd? This follows from the proof of the Cook–Levin theorem because the reduction used is parsimonious.Abhishek Shetty, Raghav Malhotra, and Chandan Saha. Lecture 26 scribe notes from Computational Complexity Theory class, 2015.

⊕P is a counting class, and can be seen as finding the least significant bit of the answer to the corresponding #P problem. The problem of finding the most significant bit is in PP. PP is believed to be a considerably harder class than ⊕P; for example, there is a relativized universe (see oracle machine) where P = ⊕P ≠ NP = PP = EXPTIME, as shown by Beigel, Buhrman, and Fortnow in 1998.

While Toda's theorem shows that P****PP contains PH, the class P⊕P is not known to even contain NP. However, the first part of the proof of Toda's theorem shows that BPP⊕P contains PH. Lance Fortnow has written a concise proof of this theorem.{{citation

⊕P contains the graph automorphism problem, and in fact this problem is low for ⊕P.{{citation

The ⊕ symbol in the name of the class may be a reference to use of the symbol ⊕ in Boolean algebra to refer the exclusive disjunction operator. This makes sense because if we consider "accepts" to be 1 and "not accepts" to be 0, the result of the machine is the exclusive disjunction of the results of each computation path.