3
$\begingroup$

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!

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

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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