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

---

$\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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x} , Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varepsilon > 0} , as well as with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-2^{poly(n)}} .
• If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} is closed under majority reductions, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle BP \cdot \mathcal{C} \subseteq \exists \cdot \forall \cdot \mathcal{C} \cap \forall \cdot \exists \cdot \mathcal{C}} .
• If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} is closed under majority reductions, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V \in \mathcal{C}} do not define a language Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle BP\cdot } P = BPP.
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle BP \cdot NP = AM}
• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists \cdot BPP = MA} (not to be confused with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \exists} BPP!)

---