Zoo Operators

co: Complements

Definition: A language L is in $\exists \cdot {\mathcal {C}}$ if $L^{c}=\{x:x\notin L\}$ is in ${\mathcal {C}}$ .

Properties: $co\cdot co\cdot {\mathcal {C}}={\mathcal {C}}$

Prominent examples: $co\cdot NP=coNP$ .

$\exists$ : Existential (polynomial)

Definition: A language L is in $\exists \cdot {\mathcal {C}}$ if there exists a polynomial p and a language $V\in {\mathcal {C}}$ such that, for all strings $x$ , $x$ is in L if and only if there exists a string y, of length $|y|\leq p(|x|)$ such that $(x,y)\in V$ .

Properties:

$co\cdot \exists =\forall \cdot co$ and vice versa.
$\exists \cdot \exists =\exists$

Prominent examples: $\exists \cdot$ P = NP.

$\forall$ : Universal (polynomial)

Definition: A language L is in $\forall \cdot {\mathcal {C}}$ if there exists a polynomial p and a language $V\in {\mathcal {C}}$ such that, for all strings $x$ , $x$ is in L if and only if for all strings y of length $|y|\leq p(|x|)$ such that $(x,y)\in V$ .

Properties:

$co\cdot \forall =\exists \cdot co$ and vice versa.
$\forall \cdot \forall =\forall$

Prominent examples: $\forall \cdot$ P = coNP

BP: Bounded-error probability (two-sided)

Definition: A language L is in $BP\cdot {\mathcal {C}}$ if there exists a polynomial p and a language $V\in {\mathcal {C}}$ such that, for all strings $x$ , $Pr_{y:|y|\leq p(|x|)}[L(x)=V(x,y)]\geq 3/4$ .

Properties:

$co\cdot BP=BP\cdot co$
If ${\mathcal {C}}$ is closed under majority reductions, then $BP\cdot {\mathcal {C}}$ admits probability amplification, so we get $BP\cdot BP\cdot {\mathcal {C}}=BP\cdot {\mathcal {C}}$ , and we can replace the probability of 3/4 with $1/2+\varepsilon$ for any constant (i.e., independent of the input size |x|) $\varepsilon >0$ , as well as with $1-2^{poly(n)}$ .
If ${\mathcal {C}}$ is closed under majority reductions, then $BP\cdot {\mathcal {C}}\subseteq \exists \cdot \forall \cdot {\mathcal {C}}\cap \forall \cdot \exists \cdot {\mathcal {C}}$ .