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

Question

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.

Answer 1

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.

Answer 2

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<y_1<y_2$, 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<x_1<x_2$ 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).

Answer 3

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

Answer 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_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.