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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (x,y)\in V} .

Properties:

• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle co\cdot \exists =\forall \cdot co} and vice versa.
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \exists \cdot \exists =\exists }

Prominent examples: Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \exists \cdot } P = NP.

---

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \forall } : Universal (polynomial)

Definition: A language L is in Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle (x,y)\in V} .

Properties:

• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle co\cdot \forall =\exists \cdot co} and vice versa.
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \forall \cdot \forall =\forall }

Prominent examples: Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \forall \cdot } P = coNP

---

BP: Bounded-error probability (two-sided)

Definition: A language L is in Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle BP\cdot {\mathcal {C}}} if there exists a polynomial p and a language $V\in {\mathcal {C}}$ such that, for all strings $x$, Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle Pr_{y:|y|\leq p(|x|)}[L(x)=V(x,y)]\geq 3/4} .

Properties:

• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle co\cdot BP=BP\cdot co}
• If ${\mathcal {C}}$ is closed under majority reductions, then Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle BP\cdot {\mathcal {C}}} admits probability amplification, so we get Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle BP\cdot BP\cdot {\mathcal {C}}=BP\cdot {\mathcal {C}}} , and we can replace the probability of 3/4 with Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 1/2+\varepsilon } for any constant (i.e., independent of the input size |x|) Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \varepsilon >0} , as well as with $1-2^{poly(n)}$.
• If ${\mathcal {C}}$ is closed under majority reductions, then Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle BP\cdot {\mathcal {C}}\subseteq \exists \cdot \forall \cdot {\mathcal {C}}\cap \forall \cdot \exists \cdot {\mathcal {C}}} .
• If ${\mathcal {C}}$ is closed under majority reductions, then Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $V\in {\mathcal {C}}$ do not define a language Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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:

• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle BP\cdot } P = BPP.
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle BP\cdot NP=AM}
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \exists \cdot BPP=MA} (not to be confused with $\exists$BPP!)

---