PPP is the set of all function computation problems that admit a polynomial-time reduction to the PIGEON problem, defined as follows: A problem is PPP-complete if PIGEON is also polynomial-time reducible to it. Note that the pigeonhole principle guarantees that PIGEON is total. We can also define WEAK-PIGEON, for which the weak pigeonhole principle guarantees totality. PWPP is the corresponding class of problems that are polynomial-time reducible to it. WEAK-PIGEON is the following problem: Here, the range of the circuit is strictly smaller than its domain, so the circuit is guaranteed to be non-injective. WEAK-PIGEON reduces to PIGEON by appending a single 1 bit to the circuit's output, so PWPP PPP.
Connection to cryptography
We can view the circuit in PIGEON as a polynomial-time computable hash function. Hence, PPP is the complexity class which captures the hardness of either inverting or finding a collision in hash functions. More generally, the relationship of subclasses of FNP to polynomial-time complexity classes can be used to determine the existence of certain cryptographic primitives, and vice versa. For example, it is known that if FNP = FP, then one-way functions do not exist. Similarly, if PPP = FP, then one-way permutations do not exist. Hence, PPP more closely captures the question of the existence of one-way permutations. We can prove this by reducing the problem of inverting a permutation on an output to PIGEON. Construct a circuit that computes. Since is a permutation, a solution to PIGEON must output such that, which implies.
Relationship to PPAD
PPP contains PPAD as a subclass. This is because End-of-the-Line, which defines PPAD, admits a straightforward polynomial-time reduction to PIGEON. In End-of-the-Line, the input is a start vertex in a directed graph where each vertex has at most one successor and at most one predecessor, represented by a polynomial-time computable successor function. Define a circuit whose input is a vertex and whose output is its successor if there is one, or if it does not. If we represent the source vertex as the bitstring, this circuit is a direct reduction of End-of-the-Line to Pigeon, since any collision in provides a sink in.
Notable problems
Equal sums problem
The equal sums problem is the following problem. Given positive integers that sum to less than, find two distinct subsets of the integers that have the same total. This problem is contained in PPP, but it is not known if it is PPP-complete.
Constrained-SIS problem
The constrained-SIS problem, which is a generalization of the SIS problem from lattice-based cryptography, has been shown to be complete for PPP. Prior to that work, the only problems known to be complete for PPP were variants of PIGEON.
