PPP (complexity)
Encyclopedia
PPP is a complexity class
, standing for "Polynomial Pigeonhole Principle". Introduced by Christos Papadimitriou
in 1994 (page 528), PPP is a subclass of TFNP
. It is a class of search problems that can be shown to be total by an application of the pigeonhole principle.
PPP is defined as follows. A function computation problem belongs to PPP if it admits a polynomial-time reduction
to the problem PIGEONHOLE CIRCUIT, in which an input consists of a boolean circuit
having the same number of input bits as output bits, and a solution consists of either an input vector that is mapped to the output 0, or alternatively two distinct input vectors that are mapped to the same output. Note that it is the pigeonhole principle that guarantees that a solution must exist. A problem is complete
for the class PPP if in addition, PIGEONHOLE CIRCUIT is reducible to that problem.
PPP 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 PIGEONHOLE CIRCUIT.
At present, the only problems known to be complete for PPP are variants of PIGEONHOLE CIRCUIT; this is a deficiency of PPP, since this means that it has so far failed to capture the complexity of additional problems. However, the definition of the class PPP highlights the way that the pigeonhole principle is a generalization of the "parity argument on a directed graph" principle that assures that search problems belonging to PPAD are indeed total. It is an open question whether EQUAL SUBSETS is complete for PPP, where EQUAL SUBSETS is defined as follows: The input consists of a set of
positive integers that add up to less than 
. The problem is to find two distinct subsets of these numbers that have the same total.
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 Pigeonhole Principle". 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), PPP 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 pigeonhole principle.
PPP is defined as follows. A function computation problem belongs to PPP 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 the problem PIGEONHOLE CIRCUIT, in which an input consists of a boolean circuit
Boolean circuit
A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...
having the same number of input bits as output bits, and a solution consists of either an input vector that is mapped to the output 0, or alternatively two distinct input vectors that are mapped to the same output. Note that it is the pigeonhole principle that guarantees that a solution must exist. 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 PPP if in addition, PIGEONHOLE CIRCUIT is reducible to that problem.
PPP 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 PIGEONHOLE CIRCUIT.
At present, the only problems known to be complete for PPP are variants of PIGEONHOLE CIRCUIT; this is a deficiency of PPP, since this means that it has so far failed to capture the complexity of additional problems. However, the definition of the class PPP highlights the way that the pigeonhole principle is a generalization of the "parity argument on a directed graph" principle that assures that search problems belonging to PPAD are indeed total. It is an open question whether EQUAL SUBSETS is complete for PPP, where EQUAL SUBSETS is defined as follows: The input consists of a set of
positive integers that add up to less than . The problem is to find two distinct subsets of these numbers that have the same total.