New answers tagged check-my-answer
0
votes
Accepted
Show that there is also a randomized polynomial-time decider $M'$ for $L$ such that $w\in L \Rightarrow Pr[M(w)=1] > 0.99$
Since the decider $M$ has no false positive, there is no need for Chernoff bound. Consider $M'$ defined as follow:
run $M(x)$ $n$ times;
if $M$ returns $1$ at least once, then $M'$ returns $1$;
...
- 17k
Top 50 recent answers are included