# Zoo Operators

##### co: Complements

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

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

Prominent examples: ${\displaystyle co\cdot NP=coNP}$.

##### ${\displaystyle \exists }$: Existential (polynomial)

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

Properties:

• ${\displaystyle co\cdot \exists =\forall \cdot co}$ and vice versa.
• ${\displaystyle \exists \cdot \exists =\exists }$

Prominent examples: ${\displaystyle \exists \cdot }$ P = NP.

##### ${\displaystyle \forall }$: Universal (polynomial)

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

Properties:

• ${\displaystyle co\cdot \forall =\exists \cdot co}$ and vice versa.
• ${\displaystyle \forall \cdot \forall =\forall }$

Prominent examples: ${\displaystyle \forall \cdot }$ P = coNP

##### BP: Bounded-error probability (two-sided)

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

Properties:

• ${\displaystyle co\cdot BP=BP\cdot co}$
• If ${\displaystyle {\mathcal {C}}}$ is closed under majority reductions, then ${\displaystyle BP\cdot {\mathcal {C}}}$ admits probability amplification, so we get ${\displaystyle BP\cdot BP\cdot {\mathcal {C}}=BP\cdot {\mathcal {C}}}$, and we can replace the probability of 3/4 with ${\displaystyle 1/2+\varepsilon }$ for any constant (i.e., independent of the input size |x|) ${\displaystyle \varepsilon >0}$, as well as with ${\displaystyle 1-2^{poly(n)}}$.
• If ${\displaystyle {\mathcal {C}}}$ is closed under majority reductions, then ${\displaystyle BP\cdot {\mathcal {C}}\subseteq \exists \cdot \forall \cdot {\mathcal {C}}\cap \forall \cdot \exists \cdot {\mathcal {C}}}$.
• If ${\displaystyle {\mathcal {C}}}$ is closed under majority reductions, then ${\displaystyle \exists \cdot BP\cdot {\mathcal {C}}\subseteq BP\cdot \exists \cdot {\mathcal {C}}}$.
• Note that, because of the semantic nature of the defining condition for the BP operator, it is possible that some languages ${\displaystyle V\in {\mathcal {C}}}$ do not define a language ${\displaystyle L\in BP\cdot {\mathcal {C}}}$ using the defining formula above. Only those V which satisfy the required condition can be used.

Prominent examples: