PPP (complexity)
Introduction In computational complexity theory, the complexity class '''PPP''' ('''polynomial pigeonhole principle''') is a subclass of TFNP. It is the class of search problems that can be shown to be total by an application of the pigeonhole principle. Christos Papadimitriou introduced it in the same paper that introduced PPAD and PPA. 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.
Definition PPP is the set of all function computation problems that admit a polynomial-time reduction to the ''PIGEON'' problem, defined as follows::Given a Boolean circuit  having the same number  of input bits as output bits, find either an input  that is mapped to the output , or two distinct inputs  that are mapped to the same output .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 theweak pigeonhole principle guarantees totality. PWPP is the corresponding class of problems that are polynomial-time reducible to it. ''WEAK-PIGEON'' is the following problem::Given a Boolean circuit  having  input bits and  output bits, find  such that .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 (which is a subclass of FNP) 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 (strict containment is an open problem). 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 (short integer solution) 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''.===Integer factorization===There exist polynomial-time randomized reductions from the integer factorization problem to ''WEAK-PIGEON''. 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.
References