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]

About these ads

2 thoughts on “Pigeonhole Completeness”

I would like to follow this blog, mas couldn’t find a link to a RSS feed. I think there isn’t one. Would you mind enabling it?

kintali | June 17, 2009 at 9:28 PM

Hi Vinicius,
I will add a subscribe widget on the sidebar soon. Meanwhile, you can subscribe to this blog by visiting http://kintali.wordpress.com/feed/

Reply