Parity P

From Wikipedia, the free encyclopedia

In computational complexity theory, the complexity class {\oplus}\mathbf{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 {\oplus}\mathbf{P} problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983.

{\oplus}\mathbf{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 {\oplus}\mathbf{P}; for example, there is a relativized universe (see oracle machine) where P = {\oplus}\mathbf{P} ≠ NP = PP = EXPTIME, as shown by Beigel, Buhrman, and Fortnow in 1998. Furthermore, PPP contains PH, whereas \mathbf{P}^{{\oplus}\mathbf{P}} is not known to even contain NP.

{\oplus}\mathbf{P} contains the graph isomorphism problem, and in fact this problem is low for {\oplus}\mathbf{P}. It also trivially contains UP, since all problems in UP have either zero or one accepting paths. More generally, {\oplus}\mathbf{P} is low for itself, meaning that such a machine gains no power from being able to solve any {\oplus}\mathbf{P} problem instantly.

The \oplus symbol in the name of the class may be a reference to use of the symbol \oplus 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.

[edit] References

  • C. H. Papadimitriou and S. Zachos. Two remarks on the power of counting. In Proceedings of the 6th GI Conference in Theoretical Computer Science, Lecture Notes in Computer Science, volume 145, Springer-Verlag, pp. 269-276. 1983.
  • Complexity Zoo: +P: Parity P
  • R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions. In Proceedings of ACM STOC'98, pp. 203-208. 1998.