Pigeonhole Completeness

The Complexity of searching for Pigeonholes…….

Today’s post is about a complexity class named PPP, introduced by Papadimitriou [Papadimitriou’94]. PPP stands for Polynomial Pigeonhole Principle. It is defined to capture the complexity of problems (in TFNP), whose totality is proved using the pigeonhole principle. Following is the standard problem for PPP.

Definition : (EQUAL OUTPUTS) : Given a Boolean circuit C with n inputs and n outputs, either find an input x such that C(x)=0^n or two inputs x \neq x' such that C(x)= C(x').

Exercise : If C is a monotone circuit then EQUAL OUTPUTS is in FP.

Let us look at an example. 0-1 KNAPSACK is a well-known NP-complete problem. Given a set S of n positive integers and an integer W, the goal is to find a subset A \subseteq S whose elements sum to W. For any set S of n positive integers, if the sum of elements of S is less than 2^n-1, there exist two subsets of S with the same sum. This gives rise to “TFNP version” of 0-1 KNAPSACK. It is called EQUAL SUMS.

Definition : (EQUAL SUMS) : Given a set S of n positive integers, such that the sum of elements of S is less than 2^n-1, find two subsets of S with the same sum.

Exercise : Prove that EQUAL SUMS \in PPP.

EQUAL SUMS is not known to be in FP. Our understanding of PPP is very limited. We don’t have any natural complete problem for PPP yet. As the following exercise suggests, it is unlikely that PPP-complete problems are in FP.

Exercise : If PPP = FP then one-way permutations do not exist.

Open Problems : Is Equal Sums PPP-complete [Papadimitriou’94] ? Are there other natural problems in PPP, that are not obviously in FP ? It is known that PPAD \subseteq PPP [Papadimitriou’94]. Is there a “geometric” version of Equal Sums in PPAD ?

References :

  • [Papadimitriou’94] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994) [pdf]