1
$\begingroup$

Let $L$ to be the following problem: $$L = \{ \langle M,x,1^t \rangle \mid \text{$M$ accepts $x$ after $t$ steps with probability at least $3/4$} \}.$$ Show that if $L\in BPP$ then $NP\subseteq BPP$.

I already showed that $L$ is $BPP$-hard. I think a reduction from $3SAT$ to $L$ need to be shown (logarithmic/polynomial? not sure)

It's not clear to me how to do that - I'd be glad for guidance.

$\endgroup$
1
$\begingroup$

This is similar to the proof that PP contains NP. Given a 3SAT instance $\varphi$ on $n$ variables, construct a machine $M$ that with probability $3/4 - 2^{-n}/4$ accepts, and with probability $1/4 + 2^{-n}/4$ chooses a random truth assignment and accepts if the truth assignment satisfies $\varphi$. If $\varphi$ has $N$ satisfying assignments, then $M$ accepts with probability $$ p = \frac{3}{4} - \frac{2^{-n}}{4} + \frac{M}{2^n} \left(\frac{1}{4} + \frac{2^{-n}}{4}\right). $$ If $M = 0$ then $p < 3/4$, whereas if $M \geq 1$ then $p \geq 3/4 + 2^{-2n}/4$.

I'll let you fill in the rest of the argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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