User:Paul.w.goldberg/PPP

At present, the only problems known to be complete for PPP are variants of PIGEONHOLE CIRCUIT; this is a deficiency of PPP, since this means that it has so far failed to capture the complexity of additional problems. However, the definition of the class PPP highlights the way that the pigeonhole principle is a generalization of the "parity argument on a directed graph" principle that assures that search problems belonging to PPAD are indeed total. It is an open question whether EQUAL SUBSETS is complete for PPP, where EQUAL SUBSETS is defined as follows: The input consists of a set of ${\displaystyle n}$ positive integers that add up to less than ${\displaystyle 2^{n}}$. The problem is to find two distinct subsets of these numbers that have the same total.