The Complexity of searching for Pigeonholes…….
Today’s post is about a complexity class named , introduced by Papadimitriou [Papadimitriou'94]. 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 .
Definition : (EQUAL OUTPUTS) : Given a Boolean circuit with inputs and outputs, either find an input such that or two inputs such that .
Exercise : If is a monotone circuit then EQUAL OUTPUTS is in .
Let us look at an example. 0-1 KNAPSACK is a well-known NP-complete problem. Given a set of positive integers and an integer , the goal is to find a subset whose elements sum to . For any set of positive integers, if the sum of elements of is less than , there exist two subsets of 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 of positive integers, such that the sum of elements of is less than , find two subsets of with the same sum.
Exercise : Prove that .
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 [Papadimitriou'94]. Is there a “geometric” version of Equal Sums in PPAD ?
- [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]