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.
[1] An example of a ⊕P-complete problem (under many-one reductions) is ⊕SAT: given a Boolean formula, is the number of its satisfying assignments odd?
[2] ⊕P is a counting class, and can be seen as finding the least significant bit of the answer to the corresponding #P problem.
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.
More generally, ⊕P is low for itself, meaning that such a machine gains no power from being able to solve any ⊕P problem instantly.