Timeline for Show that if $NP\subseteq BPP$ then also $NP=RP$ - considerations about solution
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 27, 2017 at 16:57 | vote | accept | Haskell Fun | ||
| Aug 27, 2017 at 16:57 | comment | added | Haskell Fun | 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, 2017 at 16:43 | comment | added | Yuval Filmus | 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, 2017 at 16:39 | comment | added | Haskell Fun | 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, 2017 at 16:29 | history | answered | Yuval Filmus | CC BY-SA 3.0 |