PPP (complexity)

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

C

{\displaystyle C}

having the same number

n

{\displaystyle n}

of input bits as output bits, find either an input

x

{\displaystyle x}

that is mapped to the output

C

(

x

)

=

0

n

{\displaystyle C(x)=0^{n}}

, or two distinct inputs

x

≠

y

{\displaystyle x\neq y}

that are mapped to the same output

C

(

x

)

=

C

(

y

)

{\displaystyle C(x)=C(y)}

.

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:

Given a Boolean circuit

C

{\displaystyle C}

having

n

{\displaystyle n}

input bits and

n

−

1

{\displaystyle n-1}

output bits, find

x

≠

y

{\displaystyle x\neq y}

such that

C

(

x

)

=

C

(

y

)

{\displaystyle C(x)=C(y)}

.

Here, the range of the circuit is strictly smaller than its domain, so the circuit is guaranteed to be non-injective.