Consider the TFNP search problem

Given a positive integer $t$ in unary, positive integers $M$ and $N$ (in binary), and a
function from $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}M\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}M\hspace{-0.04 in}-\hspace{-0.05 in}1\hspace{-0.02 in}\}$ to $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}N\hspace{-0.05 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}N\hspace{-0.05 in}-\hspace{-0.05 in}1\hspace{-0.02 in}\}$ (as a circuit),
find $\: \operatorname{min}(t,\hspace{-0.04 in}\lceil M/N\hspace{.02 in}\rceil) \:$ distinct inputs that map to the same output.


That problem is clearly hard for the class PPP. $\:$ Is that problem known to be in PPP?

  • $\begingroup$ Note that if $M = N$ then $\min(t,\lceil M/N \rceil)\leq 1$ i.e. the problem asks for 1 distinct input (the problem is immediately solvable). $\endgroup$ – Marzio De Biasi Jul 28 '14 at 7:44
  • $\begingroup$ I propose to first work on the $M=2N+1$ case. Apparently in CS hash triple collisions are much harder to find than simple collisions, though this does not necessarily imply anything for your question. I would guess that this problem cannot be reduced to PPP, and would be related to PPA-3 the same way as PPP is related to PPA. In variants of the Borsuk-Ulam theorem when one wants a triple collision, you also have to use mod 3 instead of parity arguments. Very nice question, btw. $\endgroup$ – domotorp Jul 28 '14 at 14:17

Please see the comments below by Emil Jeřábek, so I am not that sure anymore that the problem is harder.

No, it is not known but it is harder than PPP :)

Here I focus on the $M=2N+1$ case, so $t=3$, that is, we want $3$ inputs that map to the same output. In Papadimitriou's seminal paper "On the Complexity of the Parity Argument" he defined PPA-3 similarly to PPA as the search problems reducible to the argument "If in a bipartite graph a node has degree not a multiple of 3, then there is at least another such node."

Let me define here PPAD-3 in a way similar to PPAD as the search problems reducible to the argument "If in a balanced, directed bipartite graph $(A,B;E)$ there is a node in $A$ whose outdegree is not $2$ or whose indegree is not $1$, then there is at least another such node in $A$ OR there is a node in $B$ whose outdegree is not $1$ or whose indegree is not $2$."

Just like PPAD$\subset$PPP, you can show that PPAD-3 is a subset of the problem you have defined. Unfortunately this is all the evidence I can give you as (as far as I know) PPA-3 has not been investigated much and no oracle separation results are known for it, though I don't think it would be hard to obtain some. Papadimitriou defining it as a separate class should be enough evidence that there is a good chance that they differ.

  • 1
    $\begingroup$ I find this answer fairly unconvincing. Yes, PPAD-3 is likely incomparable with PPAD, but I see no reason why it shouldn’t be included in PPP. (IOW, counting mod 2 and counting mod 3 are equally well reducible to counting.) The problem in the OP may turn out not to be in PPP as this class is generally nasty (e.g., unlike other Papadimitriou’s classes it is not known to be closed under Turing reductions), but if so, I would expect a different reason than you state. $\endgroup$ – Emil Jeřábek Jul 30 '14 at 9:17
  • $\begingroup$ @Emil: Of course you might be right, but I would guess that there is an oracle separation between any of the above classes. $\endgroup$ – domotorp Jul 30 '14 at 10:27
  • 1
    $\begingroup$ Do you have any particular idea in mind for a construction of an oracle separating PPAD-3 from PPP that does not apply to PPAD-2? I’m not aware of any oracle separation results for the pigeonhole principle that would work for one prime and not for another. $\endgroup$ – Emil Jeřábek Jul 30 '14 at 11:03
  • 1
    $\begingroup$ How does that put the original question in PPP? $\;$ $\endgroup$ – user6973 Jul 31 '14 at 3:18
  • 1
    $\begingroup$ Aha, invertible here means we can compute the list of all preimages. (I was thinking about a function $f^{-1}$ that selects one preimage, which is the kind of setup I usually encounter in the context of a pigeonhole principle.) Yes, the generalized php is then in PPP. However, I wouldn’t say this answers the original question, since being given an inverse is a substantial restriction, even in the case of ordinary php (i.e., $t=2$). This is most striking for the weak php, say $2N\to N$: it has a randomized polynomial-time solution if given an inverse, but if not, it can find collisions ... $\endgroup$ – Emil Jeřábek Jul 31 '14 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy