HiveBrain v1.2.0
Get Started
← Back to all entries
principleMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
overlinetextdifferencesbppbetweenand

Problem

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!

Solution

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

Context

StackExchange Computer Science Q#66067, answer score: 5

Revisions (0)

No revisions yet.