# Can we fast generate perfectly uniformly mod 3 or solve NP problem?

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) \bmod 3$, if $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.

• @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 Mar 15 '17 at 22:06
• (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 Mar 16 '17 at 8:45
• @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 Mar 16 '17 at 9:07
• 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 Mar 16 '17 at 10:15
• The downvotes are bizarre. This is a very cool question! And I see nothing unclear about it. – Sasho Nikolov Mar 18 '17 at 22:30

## 4 Answers

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<y_1<\dots<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.

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.

• 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 Mar 21 '17 at 20:51
• 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 Mar 24 '17 at 13:30
• 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 Mar 29 '17 at 18:58
• @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 Mar 30 '17 at 12:07
• ... 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 Mar 30 '17 at 12: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 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).

• 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 Mar 18 '17 at 17:52
• (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 Mar 18 '17 at 19:33
• (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 Mar 19 '17 at 6:20
• (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 Mar 19 '17 at 6:31
• 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 Mar 19 '17 at 8:32

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$.

• 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 Mar 21 '17 at 8:23
• Yes, although i'm not certain that uniqueness is necessary, or one can get away with something significantly weaker. – daniello Mar 21 '17 at 8:39
• Uniqueness of what? – Emil Jeřábek Mar 21 '17 at 9:57
• "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 Mar 21 '17 at 11:17
• 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 Mar 21 '17 at 11:34

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_1<r_2$, we fiddle around so that we kill a 1, and if $r_1>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.

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.