# if $L\in BPP$ then $NP\subseteq BPP$

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.

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