It is the class of search problems that can be shown to be total by an application of the pigeonhole principle.
[1] PPP contains both PPAD and PWPP (polynomial weak pigeonhole principle) as subclasses.
These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as one-way permutations and collision-resistant hash functions.
Note that the pigeonhole principle guarantees that PIGEON is total.
We can also define WEAK-PIGEON, for which the weak pigeonhole principle guarantees totality.
WEAK-PIGEON reduces to PIGEON by appending a single 1 bit to the circuit's output, so PWPP
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.
Similarly, if PPP = FP, then one-way permutations do not exist.
[3] Hence, PPP (which is a subclass of FNP) more closely captures the question of the existence of one-way permutations.
This is because End-of-the-Line, which defines PPAD, admits a straightforward polynomial-time reduction to PIGEON.
, this circuit is a direct reduction of End-of-the-Line to Pigeon, since any collision in
The constrained-SIS (short integer solution) problem, which is a generalization of the SIS problem from lattice-based cryptography, has been shown to be complete for PPP.
[4] Prior to that work, the only problems known to be complete for PPP were variants of PIGEON.
There exist polynomial-time randomized reductions from the integer factorization problem to WEAK-PIGEON.
[5] Additionally, under the generalized Riemann hypothesis, there also exist deterministic polynomial reductions.
However, it is still an open problem to unconditionally show that integer factorization is in PPP.