PPA (complexity)
Encyclopedia
PPA is a complexity class
, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou
in 1994 (page 528), PPA is a subclass of TFNP
. It is a class of search problems that can be shown to be total by an application of the handshaking lemma
: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem).
PPA is defined as follows. Suppose we have a graph on whose vertices are n-bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently perform local exploration.) Suppose furthermore that a specific vertex (say the all-zeroes vector) has an odd number of neighbors. We are required to find another odd-degree vertex. Note that this problem is in NP - given a solution it may be verified using the circuit that the solution is correct. A function computation problem belongs to PPA if it admits a polynomial-time reduction
to this graph search problem. A problem is complete
for the class PPA if in addition, this graph search problem is reducible to that problem.
PPA contains PPAD as a subclass. This is because the corresponding problem that defines PPAD, known as END OF THE LINE, can be reduced (in a straightforward way) to the above search for an additional odd-degree vertex (essentially, just by ignoring the directions of the edges in END OF THE LINE).
There is an un-oriented version of the Sperner lemma known to be complete for PPA. The problem of searching for a second Hamiltonian cycle on a 3-regular graph is a member of PPA, but is not known to be complete for PPA.
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:...
, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou
Christos Papadimitriou
Christos Harilaos Papadimitriou is a Professor in the Computer Science Division at the University of California, Berkeley, United States...
in 1994 (page 528), PPA is a subclass of TFNP
TFNP
In computational complexity theory, the complexity class TFNP is a subclass of FNP where a solution is guaranteed to exist. It stands for "Total Function Nondeterministic Polynomial."...
. It is a class of search problems that can be shown to be total by an application of the handshaking lemma
Handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree...
: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem).
PPA is defined as follows. Suppose we have a graph on whose vertices are n-bit binary strings, and the graph is represented by a polynomial-sized circuit that takes a vertex as input and outputs its neighbors. (Note that this allows us to represent an exponentially-large graph on which we can efficiently perform local exploration.) Suppose furthermore that a specific vertex (say the all-zeroes vector) has an odd number of neighbors. We are required to find another odd-degree vertex. Note that this problem is in NP - given a solution it may be verified using the circuit that the solution is correct. A function computation problem belongs to PPA if it admits a polynomial-time reduction
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
to this graph search problem. A problem is complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...
for the class PPA if in addition, this graph search problem is reducible to that problem.
PPA contains PPAD as a subclass. This is because the corresponding problem that defines PPAD, known as END OF THE LINE, can be reduced (in a straightforward way) to the above search for an additional odd-degree vertex (essentially, just by ignoring the directions of the edges in END OF THE LINE).
There is an un-oriented version of the Sperner lemma known to be complete for PPA. The problem of searching for a second Hamiltonian cycle on a 3-regular graph is a member of PPA, but is not known to be complete for PPA.