$\textbf{BPP}$ is usually defined in terms of probabilistic polynomial-time TMs which have an error probability of at most $\frac{1}{3}$. Furthermore, using the Chernoff bound it can be proven that the definition of $\textbf{BPP}$ is robust (i.e., the class remains the same) if we require the error probability to be upper-bounded by $\varepsilon(n) = \frac{1}{2^{p(n)}}$, where $p$ is a polynomial and $n$ denotes the input length.

Do we know what happens if we require (asymptotically speaking) smaller and smaller error probabilities? In particular, do we know whether $\textbf{BPP}$ is robust if we choose the error probability to be, say, upper-bounded by $\varepsilon(n) = \frac{1}{2^{2^n}}$?

I thought this could be shown using (again) the Chernoff bound $$\text{P}(|\bar{X} - \mu| \ge \varepsilon) \le e^{-2\varepsilon^2 m}$$ (where $\bar{X}$ is the mean value of $m$ independent samples, $\mu$ is the expectation (i.e., the PPT's error probability), and $\varepsilon \in (0, \mu]$), but I don't see a way to do so except taking $m = 2^n$ exponentially many samples.

  • 2
    $\begingroup$ Since a BPP algorithm runs in polynomial time, if its error probability is $1/2^{n^{\omega(1)}}$, then it actually makes no error at all. $\endgroup$ – Yuval Filmus Feb 19 at 11:26

Your Answer

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

Browse other questions tagged or ask your own question.