<p>I will use numbers starting from <span class="math-container">$0$</span> rather than <span class="math-container">$1$</span>, as I find it much more natural.</p>
<p>Here are two classes of problems we can solve in this way:</p>
<ol>
<li><p><strong><a href="https://en.wikipedia.org/wiki/Function_%28mathematics%29" rel="noreferrer">Functions</a> in TFNP (i.e., single-valued total NP search problems)</strong></p>
<p>(This generalizes the example with one-way permutations. It includes as a special case decision problems from <span class="math-container">$\mathrm{UP\cap coUP}$</span>.)</p>
<p>The setup is that we have a polynomial-time predicate <span class="math-container">$R(x,y)$</span>, and a polynomial <span class="math-container">$p(n)$</span> such that for every <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>, there exists a unique <span class="math-container">$y$</span> of length <span class="math-container">$m=p(n)$</span> such that <span class="math-container">$R(x,y)$</span> holds. The computational task is, given <span class="math-container">$x$</span>, find <span class="math-container">$y$</span>.</p>
<p>Now, I will assume wlog that <span class="math-container">$m$</span> is even, so that <span class="math-container">$2^m\equiv 1\pmod3$</span>. The algorithm is to generate a uniformly random <span class="math-container">$y\in[0,2^m)$</span>, and output</p>
<ul>
<li><p><span class="math-container">$y$</span> (as a solution of the search problem) if <span class="math-container">$R(x,y)$</span>;</p>
</li>
<li><p><span class="math-container">$y-y'$</span> (as a random element of <span class="math-container">$\{0,1,2\}$</span>) if <span class="math-container">$y-y'\in\{1,2\}$</span>, and <span class="math-container">$R(x,y')$</span>;</p>
</li>
<li><p><span class="math-container">$y\bmod3$</span> (as a random element of <span class="math-container">$\{0,1,2\}$</span>) if no <span class="math-container">$y'\in\{y,y-1,y-2\}$</span> solves <span class="math-container">$R(x,y')$</span>.</p>
</li>
</ul>
<p>If there were no solution of the search problem, the <span class="math-container">$2^m$</span> random choices would give <span class="math-container">$1$</span> and <span class="math-container">$2$</span> <span class="math-container">$(2^m-1)/3$</span> times, and <span class="math-container">$0$</span> <span class="math-container">$(2^m+2)/3$</span> times (one more). However, if <span class="math-container">$y$</span> solves the search problem, we tinkered with the elements <span class="math-container">$y,y+1,y+2$</span> (which hit all three residue classes) so that they only produce residues <span class="math-container">$1$</span> and <span class="math-container">$2$</span>, which evens out the advantage of <span class="math-container">$0$</span>. (I am assuming here wlog that <span class="math-container">$y&lt;2^m-2$</span>.)</p>
</li>
<li><p><strong>PPA-<span class="math-container">$3$</span> search problems</strong></p>
<p>A convenient way to define PPA-<span class="math-container">$3$</span> is as NP search problems many-one reducible to the following kind of problems. We have a fixed polynomial-time function <span class="math-container">$f(x,y)$</span>, and a polynomial <span class="math-container">$p(n)$</span>, such that for any input <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>, the induced mapping <span class="math-container">$f_x(y)=f(x,y)$</span> restricted to inputs <span class="math-container">$y$</span> of length <span class="math-container">$m=p(n)$</span> is a function <span class="math-container">$f_x\colon[0,2^m)\to[0,2^m)$</span> satisfying <span class="math-container">$f_x(f_x(f_x(y)))=y$</span> for every <span class="math-container">$y$</span>. The task is, given <span class="math-container">$x$</span>, find a fixpoint <span class="math-container">$y$</span> of <span class="math-container">$f_x$</span>: <span class="math-container">$f_x(y)=y$</span>.</p>
<p>We can solve this in the way in the question as follows: given <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>, we generate a random <span class="math-container">$y$</span> of length <span class="math-container">$m=p(n)$</span>, and output</p>
<ul>
<li><p><span class="math-container">$y$</span> if it is a fixpoint of <span class="math-container">$f_x$</span>;</p>
</li>
<li><p>otherwise, <span class="math-container">$y$</span>, <span class="math-container">$f_x(y)$</span>, and <span class="math-container">$f_x(f_x(y))$</span> are distinct elements. We can label them as <span class="math-container">$\{y,f_x(y),f_x(f_x(y))\}=\{y_0,y_1,y_2\}$</span> with <span class="math-container">$y_0&lt;y_1&lt;y_2$</span>, and output <span class="math-container">$i\in\{0,1,2\}$</span> such that <span class="math-container">$y=y_i$</span>.</p>
</li>
</ul>
<p>It is clear from the definitions that this gives a uniform distribution on <span class="math-container">$\{0,1,2\}$</span>, as the non-fixpoint <span class="math-container">$y$</span>'s come in triples.</p>
</li>
</ol>
<hr />
<p>Let me show for the record the equivalence of the problem above with Papadimitriou’s complete problem for PPA-<span class="math-container">$3$</span>, as this class is mostly neglected in the literature. The problem is mentioned in Buss, Johnson: “Propositional proofs and reductions between NP search problems”, but they do not state the equivalence. For PPA, a similar problem (LONELY) is given in Beame, Cook, Edmonds, Impagliazzo, and Pitassi: “The relative complexity of NP search problems”. There is nothing special about <span class="math-container">$3$</span>, the argument below works mutatis mutandis for any odd prime.</p>
<blockquote>
<p><strong>Proposition:</strong> The following NP search problems are poly-time many-one reducible to each other:</p>
<ol>
<li><p>Given a circuit representing a bipartite undirected graph <span class="math-container">$(A\cup B,E)$</span>, and a vertex <span class="math-container">$u\in A\cup B$</span> whose degree is not divisible by <span class="math-container">$3$</span>, find another such vertex.</p>
</li>
<li><p>Given a circuit representing a directed graph <span class="math-container">$(V,E)$</span>, and a vertex <span class="math-container">$u\in V$</span> whose degree balance (i.e., out-degree minus in-degree) is not divisible by <span class="math-container">$3$</span>, find another such vertex.</p>
</li>
<li><p>Given a circuit computing a function <span class="math-container">$f\colon[0,2^n)\to[0,2^n)$</span> such that <span class="math-container">$f^3=\mathrm{id}$</span>, find a fixpoint of <span class="math-container">$f$</span>.</p>
</li>
</ol>
</blockquote>
<p><strong>Proof:</strong></p>
<p><span class="math-container">$1\le_p2$</span> is obvious, as it suffices to direct the edges from left to right.</p>
<p><span class="math-container">$2\le_p1$</span>: First, let us construct a weighted bipartite graph. Let <span class="math-container">$A$</span> and <span class="math-container">$B$</span> be copies of <span class="math-container">$V$</span>: <span class="math-container">$A=\{x^A:x\in V\}$</span>, <span class="math-container">$B=\{x^B:x\in V\}$</span>. For each original edge <span class="math-container">$x\to y$</span>, we put in an edge <span class="math-container">$\{x^A,y^B\}$</span> of weight <span class="math-container">$1$</span>, and an edge <span class="math-container">$\{x^B,y^A\}$</span> of weight <span class="math-container">$-1$</span>. This makes <span class="math-container">$\deg(x^A)=-\deg(x^B)$</span> equal to the degree balance of <span class="math-container">$x$</span> in the original graph. If <span class="math-container">$u$</span> is the given vertex of balance <span class="math-container">$b\not\equiv0\pmod3$</span>, we add an extra edge <span class="math-container">$\{u^A,u^B\}$</span> of weight <span class="math-container">$b$</span>, so that <span class="math-container">$\deg(u^A)=2b\not\equiv0\pmod3$</span>, and <span class="math-container">$\deg(u^B)=0$</span>. <span class="math-container">$u^A$</span> will be our chosen vertex.</p>
<p>In order to make the graph a plain unweighted undirected graph, we first reduce all weights modulo <span class="math-container">$3$</span>, and drop all edges of weight <span class="math-container">$0$</span>. This leaves only edges of weights <span class="math-container">$1$</span> and <span class="math-container">$2$</span>. The latter can be replaced with suitable gadgets. For example, instead of a weight-<span class="math-container">$2$</span> edge <span class="math-container">$\{x^A,y^B\}$</span>, we include new vertices <span class="math-container">$w_i^A$</span>, <span class="math-container">$z_i^B$</span> for <span class="math-container">$i=0,\dots,3$</span>, with edges <span class="math-container">$\{x^A,y^B\}$</span>, <span class="math-container">$\{x^A,z^B_i\}$</span>, <span class="math-container">$\{w^A_i,y^B\}$</span>, <span class="math-container">$\{w^A_i,z^B_i\}$</span>, <span class="math-container">$\{w^A_i,z^B_{(i+1)\bmod4}\}$</span>: this makes <span class="math-container">$\deg(w_i^A)=\deg(z_i^B)=3$</span>, and contributes <span class="math-container">$5\equiv2\pmod3$</span> to <span class="math-container">$x^A$</span> and <span class="math-container">$y^B$</span>.</p>
<p><span class="math-container">$3\le_p2$</span>: Let me assume for simplicity <span class="math-container">$n$</span> is even so that <span class="math-container">$2^n\equiv1\pmod3$</span>. We construct a directed graph on <span class="math-container">$V=[0,2^n)$</span> as follows:</p>
<ul>
<li><p>We include edges <span class="math-container">$3x+1\to3x$</span> and <span class="math-container">$3x+2\to3x$</span> for each <span class="math-container">$x&lt;2^n/3-1$</span>.</p>
</li>
<li><p>If <span class="math-container">$x_0&lt;x_1&lt;x_2$</span> is a non-fixpoint orbit of <span class="math-container">$f$</span>, we include edges <span class="math-container">$x_0\to x_1$</span> and <span class="math-container">$x_0\to x_2$</span>.</p>
</li>
</ul>
<p>The chosen vertex will be <span class="math-container">$u=2^n-1$</span>. The first clause contributes balance <span class="math-container">$1$</span> or <span class="math-container">$-2\equiv1\pmod3$</span> to each vertex <span class="math-container">$\ne u$</span>. Likewise, the second clause contributes balance <span class="math-container">$-1$</span> or <span class="math-container">$2\equiv-1\pmod3$</span> to vertices that are not fixpoints. Thus, assuming <span class="math-container">$u$</span> is not already a fixpoint, it is indeed unbalanced modulo <span class="math-container">$3$</span>, and any other vertex unbalanced modulo <span class="math-container">$3$</span> is a fixpoint of <span class="math-container">$f$</span>.</p>
<p><span class="math-container">$1\le_p3$</span>: We may assume that <span class="math-container">$A=B=[0,2^n)$</span> with <span class="math-container">$n$</span> even, and the given vertex <span class="math-container">$u\in A$</span> has degree <span class="math-container">$\equiv2\pmod3$</span>.</p>
<p>We can efficiently label edges incident with a vertex <span class="math-container">$y\in B$</span> as <span class="math-container">$(y,j)$</span>, where <span class="math-container">$j&lt;\deg(y)$</span>. In this way, <span class="math-container">$E$</span> becomes a subset of <span class="math-container">$[0,2^n)\times[0,2^n)$</span>, which we identify with <span class="math-container">$[0,2^{2n})$</span>. We define a function <span class="math-container">$f$</span> on <span class="math-container">$[0,2^n)\times[0,2^n)$</span> as follows.</p>
<ul>
<li><p>On the complement of <span class="math-container">$E$</span>: for each <span class="math-container">$y\in B$</span>, and <span class="math-container">$j$</span> such that <span class="math-container">$\deg(y)\le 3j&lt;2^n-1$</span>, we make <span class="math-container">$f(y,3j)=(y,3j+1)$</span>, <span class="math-container">$f(y,3j+1)=(y,3j+2)$</span>, <span class="math-container">$f(y,3j+2)=(y,3j)$</span>. Also, <span class="math-container">$f(3i,2^n-1)=(3i+1,2^n-1)$</span>, <span class="math-container">$f(3i+1,2^n-1)=(3i+2,2^n-1)$</span>, <span class="math-container">$f(3i+2,2^n-1)=(3i,2^n-1)$</span> for <span class="math-container">$3i&lt;2^n-1$</span>. This leaves out the point <span class="math-container">$(2^n-1,2^n-1)$</span>, and <span class="math-container">$3-(\deg(y)\bmod 3)$</span> points <span class="math-container">$(y,i)$</span> for each <span class="math-container">$y\in B$</span> whose degree is not divisible by <span class="math-container">$3$</span>.</p>
</li>
<li><p>On <span class="math-container">$E$</span>: for each <span class="math-container">$x\in A$</span>, we fix an efficient enumeration of its incident edges <span class="math-container">$(y_0,j_0),\dots,(y_{d-1},j_{d-1})$</span>, where <span class="math-container">$d=\deg(x)$</span>. We put <span class="math-container">$f(y_{3i},j_{3i})=(y_{3i+1},j_{3i+1})$</span>, <span class="math-container">$f(y_{3i+1},j_{3i+1})=(y_{3i+2},j_{3i+2})$</span>, <span class="math-container">$f(y_{3i+2},j_{3i+2})=(y_{3i},j_{3i})$</span> for <span class="math-container">$i&lt;\lfloor d/3\rfloor$</span>. This leaves out <span class="math-container">$\deg(x)\bmod3$</span> points for each vertex <span class="math-container">$x\in A$</span> whose degree is not divisible by <span class="math-container">$3$</span>.</p>
</li>
</ul>
<p>Since <span class="math-container">$\deg(u)\equiv2\pmod3$</span>, two of its incident edges were left out; we make them into yet another <span class="math-container">$f$</span> cycle using <span class="math-container">$(2^n-1,2^n-1)$</span> as the third point. The remaining points are left as fixpoints of <span class="math-container">$f$</span>. By construction, any of them will give rise to a solution of (1).</p>

CC BY-SA 3.0
2017-03-18T17:52:29.627Z
Both solutions are correct, but I have a problem with the definitions of the classes. In the definition of TFNP, usually at least one solution is required to exist, while you want exactly one, which would be TFUP, I guess. PPA-3 is originally defined with input a bipartite graph and a given vertex whose degree is not 3, and we need to find another such vertex. Your example with $f$ is obviously in this class, but why is it complete for it? (This might be well-known, but it's new to me.)
domotorp
CC BY-SA 3.0
2017-03-18T19:33:26.717Z
(1) I stressed very explicitly that the result does not apply to arbitrary TFNP search problems, but only to functions. I really don’t know how to make it even more clear.  (2) Yes, this is equivalent to the usual definition of PPA-3. This shouldn’t be difficult to show.
Emil Jeřábek
CC BY-SA 3.0
2017-03-19T06:20:14.803Z
(1) Sorry, here my confusion was only linguistic; in your original comment you've indeed emphasized single valued, but in your answer you wrote just TFNP functions, and then added in parenthesis the "i.e." which makes equivalent as far as I know. I think it would be easier to understand if you wrote "single-valued TFNP functions" in your answer too.
domotorp
CC BY-SA 3.0
2017-03-19T06:31:06.107Z
(2) This equivalence would be very surprising. With a similar trick that you've used in (1), it would imply that USAT is in PPA-3, wouldn't it? I would expect it more probable that my problem is related to some TFNP whose number of solutions is 1 or 2 mod 3 for each $n$ (and we need to know which). Btw, your solution for (1) already implies that FullFactoring can be solved, which was my original motivation.
domotorp
CC BY-SA 3.0
2017-03-19T08:32:18.833Z
Functions *are* single-valued. That's what function means. I'll try to look up the stuff on PPA-3. However, I don't see how it would include USAT. The construction in (1) does not produce a poly-time $f$ with $f^3=\mathrm{id}$, or at least I don't see it: for the obvious choice,  one cannot compute $f(2^m-1)$ without solving the search problem first.
Emil Jeřábek
CC BY-SA 3.0
2017-03-19T12:19:12.653Z
(1) I see, so you mean that the relation in the definition of TFNP is a function! I'm sorry, but I've never encountered this thing called such before. (2) You are right, it doesn't work. Still, I would be very interested to know if your definition of PPA-3 is equivalent to the original. I suppose if so, the analogous definition with $f^2=id$ would be equivalent to PPA.
domotorp
CC BY-SA 3.0
2017-03-19T17:00:22.587Z
The analogous problem with $f^2=\mathrm{id}$ is indeed well known to be equivalent to PPA: this is a notational variant of the problem called LONELY in “The relative complexity of NP search problems” by Beame, Cook, Edmonds, Impagliazzo, and Pitassi. (Note that while $2^n$ is not divisible by $3$, it is divisible by $2$, so the problem needs to be formulated in a slightly more complicated way: given an involution on $[0,2^n)$, and a fixpoint, find *another* fixpoint. Alternatively, use an odd-size domain instead of $[0,2^n)$.)
Emil Jeřábek
CC BY-SA 3.0
2017-03-20T13:10:14.710Z
Yeah, their proof works for PPA-3 as well; just take 3 copies of each vertex from one class of the bipartite graph, and 6 copies of each vertex from the other class. This makes me wonder even more what the possible common generalization of (1) and (2) is.
domotorp
CC BY-SA 3.0
2017-03-21T04:04:26.793Z
I saw your reductions related to PPA-3, I believe they are correct.
domotorp
CC BY-SA 3.0
2017-03-18T15:04:16.840Z
2017-03-20T18:56:01.340Z
2020-06-17T09:38:08.363Z
Emil Jeřábek
<p>If you could perfectly generate mod $3$ OR solve SAT (or any other NP-complete problem, for that matter) then $NP = coNP$. In particular, consider the perfect generator / solver when given a SAT formula $\phi$.</p>

<p>Let $\ell(n)$ be the maximum number of random bits drawn by the generator on inputs of size $n$. Since the generator runs in polynomial time, $\ell(n)$ is polynomial. Since $2^{\ell(n)}$ is not divisible by $3$ there must be some sequence of at most $\ell(n)$ coin tosses that will make the generator output a (correct) answer for $\phi$. Thus, if $\phi$ is unsatisfiable, there is a set of coin tosses that make the generator say that $\phi$ is unsatisfiable. If $\phi$ is satisfiable then the generator will never wrongly claim that $\phi$ is unsatisfiable, no matter what the coins are. Thus, we have shown that the language $UNSAT$ of unsatisfiable formulas is in $NP$, implying $NP = coNP$.    </p>

CC BY-SA 3.0
2017-03-21T08:23:50.703Z
In other words: whatever we can solve in this way is reducible to a TFNP problem. So, rather than NP,  we sould shoot for subclasses of TFNP.
Emil Jeřábek
CC BY-SA 3.0
2017-03-21T08:39:29.190Z
Yes, although i'm not certain that uniqueness is necessary, or one can get away with something significantly weaker.
daniello
CC BY-SA 3.0
2017-03-21T09:57:14.417Z
Uniqueness of what?
Emil Jeřábek
CC BY-SA 3.0
2017-03-21T11:17:56.823Z
"The setup is that we have a polynomial-time predicate $R(x,y)$, and a polynomial $p(n)$ such that for every $x$ of length $n$, there exists a **unique** $y$ of length $m=p(n)$ such that $R(x,y)$ holds. The computational task is, given $x$, find $y$." I have a feeling that the number of $y$'s not being divisible by $3$ could be enough. [Just noticed domotorp's new answer]
daniello
CC BY-SA 3.0
2017-03-21T11:34:12.433Z
Well, the first part of my answer is about search problems with a unique solution, but that of course is not necessary. Already the second part of my answer is about search problems with potentially many solutions. What I meant by my comment above is the simple observation that if $A(x)$ is a randomized poly-time algorithm that either generates a uniformly random element of $\{0,1,2\}$, or solves a problem $S$, then “given $x$, compute a string of random bits that makes $A$ solve $S$” is a TFNP problem, and $S$ is reducible to it. No uniqueness involved.
Emil Jeřábek
CC BY-SA 3.0
2017-03-20T21:39:55.763Z
2017-03-20T22:33:40.147Z
2017-03-20T22:33:40.147Z
daniello
<p>So here is an extension of Emil's argument that shows that search problems where the number of solutions is 1, 2 or 4 (we do not need to know which) can be solved in the above way.
I'm posting it as an answer because it's way too long for a comment and I hope that someone smarter than me can prove that in fact the number of solutions can be anything not divisible by 3.</p>

<p>Say that a random string $r$ is <em>close</em> to a solution (i.e., to a $y$ for which $R(x,y)$ holds) if one of $R(x,r)$, $R(x,r+1)$, or $R(x,r+2)$ holds.
(For simplicity, suppose that $y=0$ and $y=1$ are not solutions.)
In Emil's solution, it was enough to generate a random string $r$ and output $r\bmod 3$ except that we locally <em>fiddle around</em> at solutions; I don't go into details, see his answer.
It is enough for us that if $r$ is close to a solution, then we can <em>kill</em> an arbitrary number$\bmod 3$ by possibly outputting a solution so that for the rest of the $r$'s the $r\bmod 3$ function gives a perfectly uniform number$\bmod 3$.</p>

<p>Now, let us suppose that the number of solutions is 1 or 2 for any $x$.
We generate two random strings of length $n$: $r_1$ and $r_2$.
If at least one of them is not close to a solution, we output $r_1+r_2\bmod 3$.
For simplicity, suppose that $n$ is even so that we have an extra 0 if we just did this, and also suppose that if there are two solutions, they are far.
If $r_1$ and $r_2$ are both close to the same solution, we fiddle around so that we kill a 0.
If $r_1$ and $r_2$ are close to different solutions, then if $r_1&lt;r_2$, we fiddle around so that we kill a 1, and if $r_1&gt;r_2$, we fiddle around so that we kill a 2.
This way if there is only one solution, we kill exactly one 0, while if there are two solutions, we kill two 0's, and one 1 and one 2.</p>

<p>This argument cannot be extended to 3 solutions, but can be for 4, and from here I'll be very sketchy.
Generate four random strings, $r_1,r_2,r_3,r_4$ and output $r_1+r_2+r_3+r_4 \bmod 3$ unless all of them are close to a solution.
Again suppose that there's an extra 0 and solutions are always far.
If all the $r_i$'s are close to the same solution, we fiddle around to kill a 0.
If three of the $r_i$'s are close to the same solution that is smaller than the solution to which the fourth $r_i$ is close, we fiddle around to kill a 1.
If three of the $r_i$'s are close to the same solution that is larger than the solution to which the fourth $r_i$ is close, we fiddle around to kill a 2.
If all the $r_i$'s are close to a different solution, we kill three 0's.
The correctness for one and two solutions is similar to the previous case.
For four solutions, notice that we kill four+three 0's, six 1's and six 2's.</p>

<p>I think that the reasoning of the the last paragraph could be extended to any bounded number of solutions that is not divisible by 3 with some algebra.
A more interesting question is whether there is a protocol that works for any number of solutions.</p>

CC BY-SA 3.0
2017-03-21T11:11:52.250Z
2017-03-21T11:11:52.250Z
domotorp
<p>As a followup to domotorp’s answer, I believe we can solve NP search problems satisfying one the following restrictions:</p>

<ol>
<li><p>the number of solutions is known, and not divisible by $3$; or,</p></li>
<li><p>the number of solutions is polynomially bounded (but not known in advance).</p></li>
</ol>

<p>For 1., we can use simple padding to reduce to the following case:</p>

<ul>
<li><p>The solutions are from $[0,2^{m-1})$, where $m$ is even.</p></li>
<li><p>The number of solutions $s$ satisfies $s\equiv1\pmod3$.</p></li>
<li><p>Any two solutions are at least distance $4$ apart. (Say, they are all divisible by $4$.)</p></li>
</ul>

<p>Notice that $3\mid 2^m-s$. So, we can solve the problem by choosing a random $a\in[0,2^m)$, and using a similar protocol as in my answer for unique solutions if $a\in[0,2^m-s)$ (resulting in a distribution on $\{0,1,2\}$ short of one $0$ per each of the $s$ solutions), and outputting $0$ if $a\in[2^m-s,2^m)$.</p>

<p>For 2., assume first that the number of solutions $s\le p(n)$ is <em>known</em>. As in <a href="https://cstheory.stackexchange.com/a/37546">https://cstheory.stackexchange.com/a/37546</a>, let $3^k$ be the largest power of $3$ that divides $s$, so that $3\nmid\binom s{3^k}$. Consider the search problem whose solutions are sequences $y_0,\dots,y_{3^k-1}$ such that $y_0&lt;y_1&lt;\dots&lt;y_{3^k-1}$, and each $y_i$ is a solution of the original problem. On the one hand, the original problem reduces to the new one. On the other hand, the number of solutions of the new problem is $\binom s{3^k}$, i.e., not divisible by $3$, and known. Thus, we are done by 1.</p>

<p>Now, if the number of solutions is bounded by $p(n)$, but not known, we run the protocol above $2^\ell$ times ($2^\ell\ge p(n)$) in parallel for each possible choice of $1\le s\le2^\ell$, and:</p>

<ul>
<li><p>if any of the threads returns a solution of the original problem, we pass one such to the output;</p></li>
<li><p>if all the threads return elements $r_1,\dots,r_{2^\ell}\in\{0,1,2\}$, we output $(r_1+r_2+\dots+r_{2^\ell})\bmod3$.</p></li>
</ul>

<p>Conditioned on the second event, $r_s$ is uniformly distributed in $\{0,1,2\}$ for $s$ being the true number of solutions of the original problem, while the other $r_i$ are independent from $r_s$, hence the whole sum is also uniformly distributed.</p>

CC BY-SA 3.0
2017-03-21T20:51:54.647Z
The common generalization of 1 and 2 is that the number of solutions comes from a polynomial-time computable list of numbers, such that the largest power of $3$ dividing any of them is polynomially bounded.
Emil Jeřábek
CC BY-SA 3.0
2017-03-24T13:30:51.837Z
Btw, do you know any *non-composite* problems where the number of solutions can be proved to be divisible by some superpolynomial power of $3$? By composite I mean something like taking the direct product of some problems where the number of solutions is divisible by $3$ - composite problems can be solved easily the above way.
domotorp
CC BY-SA 3.0
2017-03-29T18:58:39.663Z
I think that it is possible to prove that there is an oracle under which some superpolynomial power of 3 problems cannot be solved the above way.
domotorp
CC BY-SA 3.0
2017-03-30T12:07:28.597Z
@domotorp That’s interesting, I was entertaining the possibility that some sort of Valiant–Vazirani argument could be used to solve arbitrary TFNP problems. Anyway, the characterization is still incomplete. I am particularly unhappy about the restriction in this answer that the number of solutions is known, or at least comes from a polynomial-time constructible list. For one thing, the class of such problems is apparently incomparable with PPA-3 from my other answer, so it would be good to have a construction that generalizes both. AFAICS the only upper bound is that any problem solvable ...
Emil Jeřábek
CC BY-SA 3.0
2017-03-30T12:10:01.147Z
... in the above way is reducible to a TFNP problem whose number of solutions is $1$ modulo $3$ (but not known). It’s not clear to me whether to expect that this is the right class, or whether some additional restriction is needed after all.
Emil Jeřábek
CC BY-SA 3.0
2017-03-21T19:32:18.560Z
2017-03-21T19:32:18.560Z
2017-04-13T12:32:28.743Z
Emil Jeřábek
<p>To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model:
We can get integers uniformly random from $[1,2^n]$ and our goal is to output an integer uniformly random from [1,3].</p>

<p>A simple solution whose <em>expected</em> running time is polynomial is the following. Discard $2^n$ (and possibly also $2^n-1$) from $[1,2^n]$ so that the number of remaining integers is divisible by $3$ so we can take $\bmod 3$ of the generated integer.
If we get a discarded number, we generate another number, until we get a non-discarded one.</p>

<p>But what if we want to terminate surely in polynomial time?
Because of divisibility issues, the problem becomes unsolvable.
However, I wonder if we can solve the following.</p>

<blockquote>
  <p>Suppose we can generate integers uniformly random from $[1,2^n]$ and we are given a computationally hard problem.
  Our goal is to output an integer uniformly random from [1,3] or solve the hard problem.</p>
</blockquote>

<p>Here the hard problem can be factoring an integer, solving a SAT instance or anything similar.
For example, we can decode a one-way permutation $f$ as follows, if we are given some $f(x)$ (and supposing $n$ is even):
If for our random string $f(r)&lt;f(x)$, then take $f(r) \bmod 3$, if $f(r)&gt;f(x)$, then take $f(r)-1\bmod 3$.
Finally, if $f(r)=f(x)$, then we are done, as $r=x$.
(If $n$ is odd, then something similar works, just we also have to check if $f(r+1)=f(x)$ and subtract $2$ if $f(r)&gt;f(x)$.)</p>

<p><strong>Summary of answers.</strong>
Emil Jeřábek has shown that unless we can generate perfectly uniformly, we can solve any single-valued search problem from TFNP, and also from PPA-3.
On the other hand, daniello has shown that we cannot solve NP-complete problems the above way, unless NP=co-NP.</p>

CC BY-SA 3.0
2017-03-15T22:06:02.880Z
@Tayfun If $n$ is even, we need $2^n-1$ to be divisible by $3$, if $n$ is odd, that's when we need $2^n-2$ to be divisible by $3$. I'd be happy if you were more specific about which part I should be more specific about.
domotorp
CC BY-SA 3.0
2017-03-16T08:45:01.917Z
(1) You can generalize the example with one-way permutations to solving (single-valued) functions in TFNP. (2) You can solve arbitrary PPA-3 search problems.
Emil Jeřábek
CC BY-SA 3.0
2017-03-16T09:07:39.437Z
@Emil (1): How? (2): I've also thought that this might be the right complexity class, but I don't see why we could solve such problems.
domotorp
CC BY-SA 3.0
2017-03-16T10:15:26.510Z
I'll try to write it up as an answer later. Btw, the question is interesting, I don't know what's the deal with all the downvotes.
Emil Jeřábek
CC BY-SA 3.0
2017-03-16T11:15:02.463Z
@Emil I'm surprised too - it seems to be my most controversial question ever... Thanks for writing it up, no need for all the details, but a few more lines would help.
domotorp
CC BY-SA 3.0
2017-03-18T22:30:15.460Z
The downvotes are bizarre. This is a very cool question! And I see nothing unclear about it.
Sasho Nikolov
<cc.complexity-theory><np-hardness><randomized-algorithms>
Can we fast generate perfectly uniformly mod 3 or solve NP problem?
domotorp
# Can we fast generate perfectly uniformly mod 3 or solve NP problem?

(Asked by: username_0 on 2017-03-15)

To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model:
We can get integers uniformly random from $[1,2^n]$ and our goal is to output an integer uniformly random from [1,3].

A simple solution whose *expected* running time is polynomial is the following. Discard $2^n$ (and possibly also $2^n-1$) from $[1,2^n]$ so that the number of remaining integers is divisible by $3$ so we can take $\bmod 3$ of the generated integer.
If we get a discarded number, we generate another number, until we get a non-discarded one.

But what if we want to terminate surely in polynomial time?
Because of divisibility issues, the problem becomes unsolvable.
However, I wonder if we can solve the following.

> Suppose we can generate integers uniformly random from $[1,2^n]$ and we are given a computationally hard problem.
> Our goal is to output an integer uniformly random from [1,3] or solve the hard problem.

Here the hard problem can be factoring an integer, solving a SAT instance or anything similar.
For example, we can decode a one-way permutation $f$ as follows, if we are given some $f(x)$ (and supposing $n$ is even):
If for our random string $f(r)f(x)$, then take $f(r)-1\bmod 3$.
Finally, if $f(r)=f(x)$, then we are done, as $r=x$.
(If $n$ is odd, then something similar works, just we also have to check if $f(r+1)=f(x)$ and subtract $2$ if $f(r)>f(x)$.)

**Summary of answers.**
Emil Jeřábek has shown that unless we can generate perfectly uniformly, we can solve any single-valued search problem from TFNP, and also from PPA-3.
On the other hand, daniello has shown that we cannot solve NP-complete problems the above way, unless NP=co-NP.

**Tags:** cc.complexity-theory, np-hardness, randomized-algorithms
> **Comments:**
> **username_0**: @Tayfun If $n$ is even, we need $2^n-1$ to be divisible by $3$, if $n$ is odd, that's when we need $2^n-2$ to be divisible by $3$. I'd be happy if you were more specific about which part I should be more specific about.  
> **username_1**: (1) You can generalize the example with one-way permutations to solving (single-valued) functions in TFNP. (2) You can solve arbitrary PPA-3 search problems.  
> **username_0**: @Emil (1): How? (2): I've also thought that this might be the right complexity class, but I don't see why we could solve such problems.  
> **username_1**: I'll try to write it up as an answer later. Btw, the question is interesting, I don't know what's the deal with all the downvotes.  
> **username_0**: @Emil I'm surprised too - it seems to be my most controversial question ever... Thanks for writing it up, no need for all the details, but a few more lines would help.  
> **username_2**: The downvotes are bizarre. This is a very cool question! And I see nothing unclear about it.  

---

## 4 answers

### Answer by username_1 on 2017-03-21. Score: 6 | Accepted answer

As a followup to domotorp’s answer, I believe we can solve NP search problems satisfying one the following restrictions:

1. the number of solutions is known, and not divisible by $3$; or,
2. the number of solutions is polynomially bounded (but not known in advance).

For 1., we can use simple padding to reduce to the following case:

* The solutions are from $[0,2^{m-1})$, where $m$ is even.
* The number of solutions $s$ satisfies $s\equiv1\pmod3$.
* Any two solutions are at least distance $4$ apart. (Say, they are all divisible by $4$.)

Notice that $3\mid 2^m-s$. So, we can solve the problem by choosing a random $a\in[0,2^m)$, and using a similar protocol as in my answer for unique solutions if $a\in[0,2^m-s)$ (resulting in a distribution on $\{0,1,2\}$ short of one $0$ per each of the $s$ solutions), and outputting $0$ if $a\in[2^m-s,2^m)$.

For 2., assume first that the number of solutions $s\le p(n)$ is *known*. As in <https://cstheory.stackexchange.com/a/37546>, let $3^k$ be the largest power of $3$ that divides $s$, so that $3\nmid\binom s{3^k}$. Consider the search problem whose solutions are sequences $y\_0,\dots,y\_{3^k-1}$ such that $y\_0

Now, if the number of solutions is bounded by $p(n)$, but not known, we run the protocol above $2^\ell$ times ($2^\ell\ge p(n)$) in parallel for each possible choice of $1\le s\le2^\ell$, and:

* if any of the threads returns a solution of the original problem, we pass one such to the output;
* if all the threads return elements $r\_1,\dots,r\_{2^\ell}\in\{0,1,2\}$, we output $(r\_1+r\_2+\dots+r\_{2^\ell})\bmod3$.

Conditioned on the second event, $r\_s$ is uniformly distributed in $\{0,1,2\}$ for $s$ being the true number of solutions of the original problem, while the other $r\_i$ are independent from $r\_s$, hence the whole sum is also uniformly distributed.

> **Comments:**
> **username_1**: The common generalization of 1 and 2 is that the number of solutions comes from a polynomial-time computable list of numbers, such that the largest power of $3$ dividing any of them is polynomially bounded.  
> **username_0**: Btw, do you know any *non-composite* problems where the number of solutions can be proved to be divisible by some superpolynomial power of $3$? By composite I mean something like taking the direct product of some problems where the number of solutions is divisible by $3$ - composite problems can be solved easily the above way.  
> **username_0**: I think that it is possible to prove that there is an oracle under which some superpolynomial power of 3 problems cannot be solved the above way.  
> **username_1**: @domotorp That’s interesting, I was entertaining the possibility that some sort of Valiant–Vazirani argument could be used to solve arbitrary TFNP problems. Anyway, the characterization is still incomplete. I am particularly unhappy about the restriction in this answer that the number of solutions is known, or at least comes from a polynomial-time constructible list. For one thing, the class of such problems is apparently incomparable with PPA-3 from my other answer, so it would be good to have a construction that generalizes both. AFAICS the only upper bound is that any problem solvable ...  
> **username_1**: ... in the above way is reducible to a TFNP problem whose number of solutions is $1$ modulo $3$ (but not known). It’s not clear to me whether to expect that this is the right class, or whether some additional restriction is needed after all.  

---

### Answer by username_1 on 2017-03-18. Score: 10

I will use numbers starting from $0$ rather than $1$, as I find it much more natural.

Here are two classes of problems we can solve in this way:

1. **[Functions](https://en.wikipedia.org/wiki/Function_%28mathematics%29) in TFNP (i.e., single-valued total NP search problems)**

   (This generalizes the example with one-way permutations. It includes as a special case decision problems from $\mathrm{UP\cap coUP}$.)

   The setup is that we have a polynomial-time predicate $R(x,y)$, and a polynomial $p(n)$ such that for every $x$ of length $n$, there exists a unique $y$ of length $m=p(n)$ such that $R(x,y)$ holds. The computational task is, given $x$, find $y$.

   Now, I will assume wlog that $m$ is even, so that $2^m\equiv 1\pmod3$. The algorithm is to generate a uniformly random $y\in[0,2^m)$, and output

   * $y$ (as a solution of the search problem) if $R(x,y)$;
   * $y-y'$ (as a random element of $\{0,1,2\}$) if $y-y'\in\{1,2\}$, and $R(x,y')$;
   * $y\bmod3$ (as a random element of $\{0,1,2\}$) if no $y'\in\{y,y-1,y-2\}$ solves $R(x,y')$.

   If there were no solution of the search problem, the $2^m$ random choices would give $1$ and $2$ $(2^m-1)/3$ times, and $0$ $(2^m+2)/3$ times (one more). However, if $y$ solves the search problem, we tinkered with the elements $y,y+1,y+2$ (which hit all three residue classes) so that they only produce residues $1$ and $2$, which evens out the advantage of $0$. (I am assuming here wlog that $y<2^m-2$.)
2. **PPA-$3$ search problems**

   A convenient way to define PPA-$3$ is as NP search problems many-one reducible to the following kind of problems. We have a fixed polynomial-time function $f(x,y)$, and a polynomial $p(n)$, such that for any input $x$ of length $n$, the induced mapping $f\_x(y)=f(x,y)$ restricted to inputs $y$ of length $m=p(n)$ is a function $f\_x\colon[0,2^m)\to[0,2^m)$ satisfying $f\_x(f\_x(f\_x(y)))=y$ for every $y$. The task is, given $x$, find a fixpoint $y$ of $f\_x$: $f\_x(y)=y$.

   We can solve this in the way in the question as follows: given $x$ of length $n$, we generate a random $y$ of length $m=p(n)$, and output

   * $y$ if it is a fixpoint of $f\_x$;
   * otherwise, $y$, $f\_x(y)$, and $f\_x(f\_x(y))$ are distinct elements. We can label them as $\{y,f\_x(y),f\_x(f\_x(y))\}=\{y\_0,y\_1,y\_2\}$ with $y\_0, and output $i\in\{0,1,2\}$ such that $y=y\_i$.

   It is clear from the definitions that this gives a uniform distribution on $\{0,1,2\}$, as the non-fixpoint $y$'s come in triples.

---

Let me show for the record the equivalence of the problem above with Papadimitriou’s complete problem for PPA-$3$, as this class is mostly neglected in the literature. The problem is mentioned in Buss, Johnson: “Propositional proofs and reductions between NP search problems”, but they do not state the equivalence. For PPA, a similar problem (LONELY) is given in Beame, Cook, Edmonds, Impagliazzo, and Pitassi: “The relative complexity of NP search problems”. There is nothing special about $3$, the argument below works mutatis mutandis for any odd prime.

> **Proposition:** The following NP search problems are poly-time many-one reducible to each other:
>
> 1. Given a circuit representing a bipartite undirected graph $(A\cup B,E)$, and a vertex $u\in A\cup B$ whose degree is not divisible by $3$, find another such vertex.
> 2. Given a circuit representing a directed graph $(V,E)$, and a vertex $u\in V$ whose degree balance (i.e., out-degree minus in-degree) is not divisible by $3$, find another such vertex.
> 3. Given a circuit computing a function $f\colon[0,2^n)\to[0,2^n)$ such that $f^3=\mathrm{id}$, find a fixpoint of $f$.

**Proof:**

$1\le\_p2$ is obvious, as it suffices to direct the edges from left to right.

$2\le\_p1$: First, let us construct a weighted bipartite graph. Let $A$ and $B$ be copies of $V$: $A=\{x^A:x\in V\}$, $B=\{x^B:x\in V\}$. For each original edge $x\to y$, we put in an edge $\{x^A,y^B\}$ of weight $1$, and an edge $\{x^B,y^A\}$ of weight $-1$. This makes $\deg(x^A)=-\deg(x^B)$ equal to the degree balance of $x$ in the original graph. If $u$ is the given vertex of balance $b\not\equiv0\pmod3$, we add an extra edge $\{u^A,u^B\}$ of weight $b$, so that $\deg(u^A)=2b\not\equiv0\pmod3$, and $\deg(u^B)=0$. $u^A$ will be our chosen vertex.

In order to make the graph a plain unweighted undirected graph, we first reduce all weights modulo $3$, and drop all edges of weight $0$. This leaves only edges of weights $1$ and $2$. The latter can be replaced with suitable gadgets. For example, instead of a weight-$2$ edge $\{x^A,y^B\}$, we include new vertices $w\_i^A$, $z\_i^B$ for $i=0,\dots,3$, with edges $\{x^A,y^B\}$, $\{x^A,z^B\_i\}$, $\{w^A\_i,y^B\}$, $\{w^A\_i,z^B\_i\}$, $\{w^A\_i,z^B\_{(i+1)\bmod4}\}$: this makes $\deg(w\_i^A)=\deg(z\_i^B)=3$, and contributes $5\equiv2\pmod3$ to $x^A$ and $y^B$.

$3\le\_p2$: Let me assume for simplicity $n$ is even so that $2^n\equiv1\pmod3$. We construct a directed graph on $V=[0,2^n)$ as follows:

* We include edges $3x+1\to3x$ and $3x+2\to3x$ for each $x<2^n/3-1$.
* If $x\_0 is a non-fixpoint orbit of $f$, we include edges $x\_0\to x\_1$ and $x\_0\to x\_2$.

The chosen vertex will be $u=2^n-1$. The first clause contributes balance $1$ or $-2\equiv1\pmod3$ to each vertex $\ne u$. Likewise, the second clause contributes balance $-1$ or $2\equiv-1\pmod3$ to vertices that are not fixpoints. Thus, assuming $u$ is not already a fixpoint, it is indeed unbalanced modulo $3$, and any other vertex unbalanced modulo $3$ is a fixpoint of $f$.

$1\le\_p3$: We may assume that $A=B=[0,2^n)$ with $n$ even, and the given vertex $u\in A$ has degree $\equiv2\pmod3$.

We can efficiently label edges incident with a vertex $y\in B$ as $(y,j)$, where $j<\deg(y)$. In this way, $E$ becomes a subset of $[0,2^n)\times[0,2^n)$, which we identify with $[0,2^{2n})$. We define a function $f$ on $[0,2^n)\times[0,2^n)$ as follows.

* On the complement of $E$: for each $y\in B$, and $j$ such that $\deg(y)\le 3j<2^n-1$, we make $f(y,3j)=(y,3j+1)$, $f(y,3j+1)=(y,3j+2)$, $f(y,3j+2)=(y,3j)$. Also, $f(3i,2^n-1)=(3i+1,2^n-1)$, $f(3i+1,2^n-1)=(3i+2,2^n-1)$, $f(3i+2,2^n-1)=(3i,2^n-1)$ for $3i<2^n-1$. This leaves out the point $(2^n-1,2^n-1)$, and $3-(\deg(y)\bmod 3)$ points $(y,i)$ for each $y\in B$ whose degree is not divisible by $3$.
* On $E$: for each $x\in A$, we fix an efficient enumeration of its incident edges $(y\_0,j\_0),\dots,(y\_{d-1},j\_{d-1})$, where $d=\deg(x)$. We put $f(y\_{3i},j\_{3i})=(y\_{3i+1},j\_{3i+1})$, $f(y\_{3i+1},j\_{3i+1})=(y\_{3i+2},j\_{3i+2})$, $f(y\_{3i+2},j\_{3i+2})=(y\_{3i},j\_{3i})$ for $i<\lfloor d/3\rfloor$. This leaves out $\deg(x)\bmod3$ points for each vertex $x\in A$ whose degree is not divisible by $3$.

Since $\deg(u)\equiv2\pmod3$, two of its incident edges were left out; we make them into yet another $f$ cycle using $(2^n-1,2^n-1)$ as the third point. The remaining points are left as fixpoints of $f$. By construction, any of them will give rise to a solution of (1).

> **Comments:**
> **username_0**: Both solutions are correct, but I have a problem with the definitions of the classes. In the definition of TFNP, usually at least one solution is required to exist, while you want exactly one, which would be TFUP, I guess. PPA-3 is originally defined with input a bipartite graph and a given vertex whose degree is not 3, and we need to find another such vertex. Your example with $f$ is obviously in this class, but why is it complete for it? (This might be well-known, but it's new to me.)  
> **username_1**: (1) I stressed very explicitly that the result does not apply to arbitrary TFNP search problems, but only to functions. I really don’t know how to make it even more clear.  (2) Yes, this is equivalent to the usual definition of PPA-3. This shouldn’t be difficult to show.  
> **username_0**: (1) Sorry, here my confusion was only linguistic; in your original comment you've indeed emphasized single valued, but in your answer you wrote just TFNP functions, and then added in parenthesis the "i.e." which makes equivalent as far as I know. I think it would be easier to understand if you wrote "single-valued TFNP functions" in your answer too.  
> **username_0**: (2) This equivalence would be very surprising. With a similar trick that you've used in (1), it would imply that USAT is in PPA-3, wouldn't it? I would expect it more probable that my problem is related to some TFNP whose number of solutions is 1 or 2 mod 3 for each $n$ (and we need to know which). Btw, your solution for (1) already implies that FullFactoring can be solved, which was my original motivation.  
> **username_1**: Functions *are* single-valued. That's what function means. I'll try to look up the stuff on PPA-3. However, I don't see how it would include USAT. The construction in (1) does not produce a poly-time $f$ with $f^3=\mathrm{id}$, or at least I don't see it: for the obvious choice,  one cannot compute $f(2^m-1)$ without solving the search problem first.  
> **username_0**: (1) I see, so you mean that the relation in the definition of TFNP is a function! I'm sorry, but I've never encountered this thing called such before. (2) You are right, it doesn't work. Still, I would be very interested to know if your definition of PPA-3 is equivalent to the original. I suppose if so, the analogous definition with $f^2=id$ would be equivalent to PPA.  
> **username_1**: The analogous problem with $f^2=\mathrm{id}$ is indeed well known to be equivalent to PPA: this is a notational variant of the problem called LONELY in “The relative complexity of NP search problems” by Beame, Cook, Edmonds, Impagliazzo, and Pitassi. (Note that while $2^n$ is not divisible by $3$, it is divisible by $2$, so the problem needs to be formulated in a slightly more complicated way: given an involution on $[0,2^n)$, and a fixpoint, find *another* fixpoint. Alternatively, use an odd-size domain instead of $[0,2^n)$.)  
> **username_0**: Yeah, their proof works for PPA-3 as well; just take 3 copies of each vertex from one class of the bipartite graph, and 6 copies of each vertex from the other class. This makes me wonder even more what the possible common generalization of (1) and (2) is.  
> **username_0**: I saw your reductions related to PPA-3, I believe they are correct.  

---

### Answer by username_3 on 2017-03-20. Score: 7

If you could perfectly generate mod $3$ OR solve SAT (or any other NP-complete problem, for that matter) then $NP = coNP$. In particular, consider the perfect generator / solver when given a SAT formula $\phi$.

Let $\ell(n)$ be the maximum number of random bits drawn by the generator on inputs of size $n$. Since the generator runs in polynomial time, $\ell(n)$ is polynomial. Since $2^{\ell(n)}$ is not divisible by $3$ there must be some sequence of at most $\ell(n)$ coin tosses that will make the generator output a (correct) answer for $\phi$. Thus, if $\phi$ is unsatisfiable, there is a set of coin tosses that make the generator say that $\phi$ is unsatisfiable. If $\phi$ is satisfiable then the generator will never wrongly claim that $\phi$ is unsatisfiable, no matter what the coins are. Thus, we have shown that the language $UNSAT$ of unsatisfiable formulas is in $NP$, implying $NP = coNP$.

> **Comments:**
> **username_1**: In other words: whatever we can solve in this way is reducible to a TFNP problem. So, rather than NP,  we sould shoot for subclasses of TFNP.  
> **username_3**: Yes, although i'm not certain that uniqueness is necessary, or one can get away with something significantly weaker.  
> **username_1**: Uniqueness of what?  
> **username_3**: "The setup is that we have a polynomial-time predicate $R(x,y)$, and a polynomial $p(n)$ such that for every $x$ of length $n$, there exists a **unique** $y$ of length $m=p(n)$ such that $R(x,y)$ holds. The computational task is, given $x$, find $y$." I have a feeling that the number of $y$'s not being divisible by $3$ could be enough. [Just noticed domotorp's new answer]  
> **username_1**: Well, the first part of my answer is about search problems with a unique solution, but that of course is not necessary. Already the second part of my answer is about search problems with potentially many solutions. What I meant by my comment above is the simple observation that if $A(x)$ is a randomized poly-time algorithm that either generates a uniformly random element of $\{0,1,2\}$, or solves a problem $S$, then “given $x$, compute a string of random bits that makes $A$ solve $S$” is a TFNP problem, and $S$ is reducible to it. No uniqueness involved.  

---

### Answer by username_0 on 2017-03-21. Score: 4

So here is an extension of Emil's argument that shows that search problems where the number of solutions is 1, 2 or 4 (we do not need to know which) can be solved in the above way.
I'm posting it as an answer because it's way too long for a comment and I hope that someone smarter than me can prove that in fact the number of solutions can be anything not divisible by 3.

Say that a random string $r$ is *close* to a solution (i.e., to a $y$ for which $R(x,y)$ holds) if one of $R(x,r)$, $R(x,r+1)$, or $R(x,r+2)$ holds.
(For simplicity, suppose that $y=0$ and $y=1$ are not solutions.)
In Emil's solution, it was enough to generate a random string $r$ and output $r\bmod 3$ except that we locally *fiddle around* at solutions; I don't go into details, see his answer.
It is enough for us that if $r$ is close to a solution, then we can *kill* an arbitrary number$\bmod 3$ by possibly outputting a solution so that for the rest of the $r$'s the $r\bmod 3$ function gives a perfectly uniform number$\bmod 3$.

Now, let us suppose that the number of solutions is 1 or 2 for any $x$.
We generate two random strings of length $n$: $r\_1$ and $r\_2$.
If at least one of them is not close to a solution, we output $r\_1+r\_2\bmod 3$.
For simplicity, suppose that $n$ is even so that we have an extra 0 if we just did this, and also suppose that if there are two solutions, they are far.
If $r\_1$ and $r\_2$ are both close to the same solution, we fiddle around so that we kill a 0.
If $r\_1$ and $r\_2$ are close to different solutions, then if $r\_1r\_2$, we fiddle around so that we kill a 2.
This way if there is only one solution, we kill exactly one 0, while if there are two solutions, we kill two 0's, and one 1 and one 2.

This argument cannot be extended to 3 solutions, but can be for 4, and from here I'll be very sketchy.
Generate four random strings, $r\_1,r\_2,r\_3,r\_4$ and output $r\_1+r\_2+r\_3+r\_4 \bmod 3$ unless all of them are close to a solution.
Again suppose that there's an extra 0 and solutions are always far.
If all the $r\_i$'s are close to the same solution, we fiddle around to kill a 0.
If three of the $r\_i$'s are close to the same solution that is smaller than the solution to which the fourth $r\_i$ is close, we fiddle around to kill a 1.
If three of the $r\_i$'s are close to the same solution that is larger than the solution to which the fourth $r\_i$ is close, we fiddle around to kill a 2.
If all the $r\_i$'s are close to a different solution, we kill three 0's.
The correctness for one and two solutions is similar to the previous case.
For four solutions, notice that we kill four+three 0's, six 1's and six 2's.

I think that the reasoning of the the last paragraph could be extended to any bounded number of solutions that is not divisible by 3 with some algebra.
A more interesting question is whether there is a protocol that works for any number of solutions.


---

