5
$\begingroup$

Show that if $$NP ⊆ BPP$$ then $$NP = RP$$

Solution: It is enough to show that if $NP ⊆ BPP$ then $3SAT∈ RP$. Let $A$ be a $BPP$ algorithm for $3SAT$. Given a formula $ϕ$ with n variables, we first run $A$ on $ϕ$. If $A$ rejects, we reject. Otherwise, we try to construct a satisfying assignment for $ϕ$ one variable at a time. That is, we try instantiating $x_1$ to $0$, and then use $A$ to decide if the resulting formula is satisfiable: if so, then we permanently set $x_1$ to $0$ and proceed with $x_2$; otherwise we set $x_1$ to $1$ and proceed with $x_2$. If we manage to construct a satisfying assignment we accept, otherwise we reject, and so on. If $ϕ$ is unsatisfiable, then we always reject. If $ϕ$ is satisfiable, then we construct a satisfying assignment and accept provided that the $n + 1$ invocations of $A$ that we make are all correct. We can ensure that this happens with high probability by replacing each invocation of $A$ with $O(\log n)$ independent ones and taking the majority answer

It is fine solution from https://people.eecs.berkeley.edu/~luca/cs278-04/notes/sol.pdf

My only question is: Why $O(\log n)$ ? After all, we can run it polynomially to make error probablity exponetially small.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

It's true that we can run $A$ even more times, but $O(\log n)$ times suffices for us to obtain a certainty of $1 - 1/(100n)$ (say) for each $x_i$. Applying the union bound, we deduce that the algorithm finds a valid truth assignment with probability at least $1 - 1/100$.

If you run $A$ polynomially many times then you get an exponentially small error, which is not needed here.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I am not sure If I correctly understand you. Single launch of $A$ returns proper answer with $\frac{1}{p}$, where $p > 2$. So, here we can decrease it to $\frac{1}{p^{O(\log n)}}$. Using union bound, we estimate it by $\frac{n+1}{p^{O(\log n)}} $ what is something different than written by you $\endgroup$
    – Haskell Fun
    Commented Aug 27, 2017 at 16:39
  • $\begingroup$ The error from $m$ repeats doesn't quite decrease as $\epsilon^m$. We are using the majority to guess the true result, and to analyze the error probability you need to use the Chernoff bound. For example, if the error probability is $\epsilon$ then the error probability from 3 trials is $\epsilon^3 + 3\epsilon^2(1-\epsilon)$. $\endgroup$
    – Yuval Filmus
    Commented Aug 27, 2017 at 16:43
  • $\begingroup$ Ok, I tried to too simplify it. Of course, we haven't to use Chernoff, we can use another way (but proper, I made a mistake) to estimate probablistic error). Without Chernoff it is easy to estimate that launchin $2m+1$ times it is upper bounded by something exponentially small regards to $m$. $\endgroup$
    – Haskell Fun
    Commented Aug 27, 2017 at 16:57

Your Answer

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

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