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 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}} such that, for all strings 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 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 Pr_{y : |y| \leq p(|x|)}[L(x) = V(x,y)] \geq 3/4} .

Properties:

• 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 co \cdot BP = BP \cdot co}
• 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}} admits probability amplification, so we get 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 BP \cdot \mathcal{C} = BP \cdot \mathcal{C}} , and we can replace the probability of 3/4 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+\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}} .

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!)

---