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:...
is the class of decision problemDecision 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
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 #PSharp-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
; for example, there is a relativized universe (see oracle machineOracle 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 =
≠ NPNP (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
is not known to even contain NP. contains the graph isomorphism problemGraph 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
. It also trivially contains UPUP (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,
is lowLow (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
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 disjunctionExclusive 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.