Question

Show that if$\mathbf{NP}\subseteq \mathbf{BPP}$,then.$\mathbf{NP}\mathbf{=}\mathbf{RP}$

Short answer

Using the algorithm $A$and the construction of satisfying assignment which runs in spolynomial time the above problem is solved.

Step-by-step solution

 Understanding the concepts 

It can be proved by showing that if $NP\subseteq BPP$,then $SAT\in RP$.Consider a formula$\varphi$ with n

Variables $x_1,x_2,\dots x_n$be the input. $\varphi$is satisfied$\exists$truth assignment for$x_1,x_2,\dots x_n$ so that$\varphi (x_1,x_2,\dots x_n)=1$

Assume A be an BPP algorithm with error probability at most$2^{-k}$ for SAT, where$k=\left|\varphi \right|$ is the length of formula .$\varphi$ Such$A$exist because of the assumption that.$SAT\in BPP$

First run$A$on .$\varphi$ If A rejects, then reject, otherwise try to satisfy assignment for$\varphi$ on variable at a time.

Initialize$x_i$ to 0 and then call $A$to determine that if the formula resulting is satisfiable: if$A$returns “accept” then permanently set$x_i$ to 0; otherwise set $x_i$to 1. Then proceed with $x_2$similarly.

$\varphi (x_1,x_2,\dots x_n)=1$accept or otherwise rejects verify the assignment for $\varphi$if managed to construct a satisfying assignment at end.

Here is the analysis. $\varphi$Always reject either because $A$do not arrive at a satisfying assignment at the end, if it is unsatisfiable.

Continuing with the proof

On the other hand, suppose is satisfiable. Proceed to show that it accepts with probability at least.$\frac{1}{2}$

Invoke A a total of$n+1$times. If$\varphi$ is satisfiable and$A$returns “accept” each time only for an assignment for $x_i$variable which is part of a satisfying assignment, then end up with a satisfying assignment.

Now show that the probability that at least one of theinvocations return “reject” for an assignment for variable which is part of a satisfying assignment is at most.

The probability that an invocation of$A$returns does so is at most $2-k$. So, probability that encounter it is at most $(n+1){.2}^{-k}$, which is at most because.$n+1\le k$

Since both thealgorithm$A$ andthe construction of satisfying assignment run in polynomial time, the whole procedure clearly runs in polynomial time. Hence,$\mathbf{SAT}\in \mathbf{RP}$ andtherefore.$\mathbf{NP}\mathbf{=}\mathbf{RP}$