![](http://image.absoluteastronomy.com/images//topicimages/noimage.gif)
Parity P
Encyclopedia
In computational complexity theory
, the complexity class
is the class of decision problem
s 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
problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983.
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
; for example, there is a relativized universe (see oracle machine
) where P =
≠ NP
= PP = EXPTIME
, as shown by Beigel, Buhrman, and Fortnow in 1998. Furthermore, PPP contains PH, whereas
is not known to even contain NP.
contains the graph isomorphism problem
, and in fact this problem is low
for
. It also trivially contains UP
, since all problems in UP have either zero or one accepting paths. More generally,
is low
for itself, meaning that such a machine gains no power from being able to solve any
problem instantly.
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-1.gif)
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s 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
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-2.gif)
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-3.gif)
Sharp-P
In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute ƒ," where ƒ is the number of accepting paths of a nondeterministic...
problem. The problem of finding the most significant bit is in PP
PP (complexity)
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time...
. PP is believed to be a considerably harder class than
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-4.gif)
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
) where P =
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-5.gif)
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
= PP = EXPTIME
EXPTIME
In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
, as shown by Beigel, Buhrman, and Fortnow in 1998. Furthermore, PPP contains PH, whereas
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-6.gif)
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-7.gif)
Graph isomorphism problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP...
, and in fact this problem is low
Low (complexity)
In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve...
for
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-8.gif)
UP (complexity)
In complexity theory, UP is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input...
, since all problems in UP have either zero or one accepting paths. More generally,
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-9.gif)
Low (complexity)
In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve...
for itself, meaning that such a machine gains no power from being able to solve any
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-10.gif)
The
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-11.gif)
![](http://image.absoluteastronomy.com/images/formulas/2/5/2253406-12.gif)
Exclusive disjunction
The logical operation exclusive disjunction, also called exclusive or , is a type of logical disjunction on two operands that results in a value of true if exactly one of the operands has a value of true...
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.