# Is the definition of $\textbf{BPP}$ robust for doubly exponential small (or even smaller) error?

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

• 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. – Yuval Filmus Feb 19 at 11:26