# Show that if $NP\subseteq BPP$ then also $NP=RP$ - considerations about solution

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.

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.
• 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 Aug 27 '17 at 16:39
• 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)$. Aug 27 '17 at 16:43
• 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$. Aug 27 '17 at 16:57