# Differences between $\text{BPP}$ and $\overline{\text{BPP}}$ vs $\text{co-BPP}$

Is $\overline{\text{BPP}}$ different from $\text{co-BPP}$? I am having trouble understanding the "co" part of these complexities.

I think yes and here is what I think: It seems given that $\text{BPP}$ is the class of languages decided by PTMs with error probability 1/3, then this is equal to $\text{co-BPP}$. But $\overline{\text{BPP}}$ is the class of languages decided by PTMs with success probability 1/3. So $\overline{\text{BPP}}$ is different from $\text{co-BPP}$.

Am I correct on these definitions? Thanks!

• The halting problem is in $\overline{\mathrm{BPP}}$ but certainly not in co-BPP. Nov 15, 2016 at 10:30

$\newcommand{\co}{\mathsf{co}\text{-}}\co A=\left\{L\subseteq \Sigma^* \mid \overline{L}\in A\right\}$
Saying that the class $A\subseteq P\left(\Sigma^*\right)$ is closed under complement is equivalent to saying $A=\co A$ (verify).
Note that $\overline{A}$ is not the same as $\co A$, here we're simply taking all the languages outside of $A$, and we require nothing about the complement of these languages.
$\newcommand{\BPP}{\mathsf{BPP}}\BPP$ is closed under complement, since we can simply flip the answer (verify yourself that this works), so $\co \BPP=\BPP$.
$\overline{\BPP}$ however is a whole new story, and even contains all undecidable languages, since $\BPP\subseteq \mathsf{PSPACE}$.