13
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ @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. $\endgroup$
    – domotorp
    Mar 15, 2017 at 22:06
  • $\begingroup$ (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. $\endgroup$ Mar 16, 2017 at 8:45
  • $\begingroup$ @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. $\endgroup$
    – domotorp
    Mar 16, 2017 at 9:07
  • $\begingroup$ 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. $\endgroup$ Mar 16, 2017 at 10:15
  • 2
    $\begingroup$ The downvotes are bizarre. This is a very cool question! And I see nothing unclear about it. $\endgroup$ Mar 18, 2017 at 22:30

4 Answers 4

6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Mar 21, 2017 at 20:51
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Mar 24, 2017 at 13:30
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Mar 29, 2017 at 18:58
  • $\begingroup$ @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 ... $\endgroup$ Mar 30, 2017 at 12:07
  • $\begingroup$ ... 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. $\endgroup$ Mar 30, 2017 at 12:10
10
$\begingroup$

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

$\endgroup$
9
  • 1
    $\begingroup$ 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.) $\endgroup$
    – domotorp
    Mar 18, 2017 at 17:52
  • 1
    $\begingroup$ (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. $\endgroup$ Mar 18, 2017 at 19:33
  • $\begingroup$ (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. $\endgroup$
    – domotorp
    Mar 19, 2017 at 6:20
  • $\begingroup$ (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. $\endgroup$
    – domotorp
    Mar 19, 2017 at 6:31
  • $\begingroup$ 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. $\endgroup$ Mar 19, 2017 at 8:32
7
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 21, 2017 at 8:23
  • $\begingroup$ Yes, although i'm not certain that uniqueness is necessary, or one can get away with something significantly weaker. $\endgroup$
    – daniello
    Mar 21, 2017 at 8:39
  • 1
    $\begingroup$ Uniqueness of what? $\endgroup$ Mar 21, 2017 at 9:57
  • $\begingroup$ "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] $\endgroup$
    – daniello
    Mar 21, 2017 at 11:17
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 21, 2017 at 11:34
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.