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.[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? This follows from the Cook–Levin theorem because the reduction is parsimonious.[2]
⊕P is a counting class, and can be seen as finding the least significant bit of the answer to the corresponding
While Toda's theorem shows that PPP contains PH, 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.[4]
⊕P contains the
The ⊕ symbol in the name of the class may be a reference to use of the symbol ⊕ in
External links
- Complexity Zoo: Class Parity P
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.
- ^ Abhishek Shetty, Raghav Malhotra, and Chandan Saha. Lecture 26 scribe notes from Computational Complexity Theory class, 2015.
- ^ 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.
- .