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!

  • $\begingroup$ The halting problem is in $\overline{\mathrm{BPP}}$ but certainly not in co-BPP. $\endgroup$ – Raphael Nov 15 '16 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}$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.