<p>As an introductory reference to the notion of a complexity operator (and demonstrating some applications of the idea), the best I have found so far is </p>

<blockquote>
  <p>D. Kozen, Theory of Computation (Springer 2006)</p>
</blockquote>

<p>which is derived from lecture notes on computational complexity and related topics. On page 187 ("Supplementary Lecture G: Toda's Theorem"), he defines the operators</p>

<ul>
<li>$\mathsf R$ (for random certificates with bounded one-sided error, as in the class $\mathsf{RP}$)</li>
<li>$\mathsf{BP}$ (for random certificates with bounded two-sided error, see above)</li>
<li>$\mathsf P$ (for random certificates with unbounded error, c.f. $\mathsf C$ in the remarks above)</li>
<li>$\oplus$ (for an odd number of certificates, see above)</li>
<li>$\Sigma^{\mathrm{p}}$ (for existence of polynomial-length certificates, c.f. $\exists$ above)</li>
<li>$\Sigma^{\mathrm{log}}$ (for existence of $O(\log n)$-length certificates, c.f. $\exists$ above)</li>
<li>$\Pi^{\mathrm{p}}$ and $\Pi^{\mathrm{log}}$ (complementary operators to $\Sigma^{\mathrm{p}}$ and $\Sigma^{\mathrm{log}}$: see remarks on $\forall$ above)</li>
<li>$\#$ (defining a counting class, c.f. remarks above)</li>
</ul>

<p>and tacitly defines $\mathsf{co\text-}$ on page 12 in the usual way.</p>

<p>Kozen's treatment of these operators is enough to indicate how they are connected with the "usual" complexity classes, and to describe Toda's theorem, but does not much discuss their relationships and only mentions them for a total of 6 pages (in what is after all a book covering a much wider topic).
Hopefully someone can provide a better reference than this.</p>

CC BY-SA 3.0
2014-03-18T16:02:36.983Z
2014-03-18T16:02:36.983Z
Niel de Beaudrap
<p>Here is a reference with many definitions of operators (not many details though):</p>

<blockquote>
  <p>S. Zachos and A. Pagourtzis,
  <a href="http://www.cs.ucy.ac.cy/conferences/pls4/Pagourtzis.ps">Combinatory Complexity: Operators on Complexity Classes</a>, Proceedings of 4th Panhellenic Logic Symposium (PLS 2003), Thessaloniki, Jul 7-10 2003.</p>
</blockquote>

<ul>
<li><p>It defines an identity operator $\mathcal E$, as well as operators $\mathsf{co}$-&nbsp;, $\mathsf{N}$ (corresponding to $\exists$ above), $\mathsf{BP}$, $\mathsf{R}$ (corresponding to bounded one-sided error), $\oplus$, $\mathsf U$ (corresponding to non-determinism with a unique accepting transition), $\mathsf P$ (corresponding to unbounded two-sided error), and $\Delta$ (which for a class $\mathbf C$ forms $\mathbf C \cap \mathsf{co}\mathbf C$).</p></li>
<li><p>It shows that:</p>

<ol>
<li>$\mathcal E$ is an identity element with respect to composition [Definition&nbsp;1];</li>
<li>$\mathsf{co}$- is self-inverse [Definition&nbsp;2];</li>
<li>$\mathsf{N}$ is idempotent [Definition&nbsp;3] &mdash; implicit is that $\mathsf{BP}$, $\mathsf{R}$, $\oplus$, $\mathsf U$, and $\mathsf{P}$ are also idempotent;</li>
<li>$\mathsf{BP}$ and $\mathsf{P}$ commute with $\mathsf{co}$-&nbsp; [Definitions&nbsp;4 and&nbsp;8], while $\oplus$ is invariant under right-composition with $\mathsf{co}$-&nbsp;[Definition&nbsp;6];</li>
<li>The above operators are all monotone (that is, ${\mathbf C_1 \subseteq \mathbf C_2} \implies {\mathcal O\cdot\mathbf C_1 \subseteq \mathcal O\cdot\mathbf C_2}$ for all operators $\mathcal O$ above):</li>
</ol></li>
</ul>

<p>Throughout, it also describes a handful of ways that these operators relate to traditional complexity classes, such as $\mathsf{\Sigma^p_2 P}$, $\mathsf{ZPP}$, $\mathsf{AM}$, $\mathsf{MA}$, etc.</p>

CC BY-SA 3.0
2014-03-20T18:03:35.120Z
2014-03-25T15:04:20.263Z
2014-03-25T15:04:20.263Z
Alessandro Cosentino
<p>I'm interested if there exist any good expository articles or surveys to which I can refer when I write about <em>complexity class operators</em>: operators which transform complexity classes by doing things such as adding quantifiers to them.</p>

<h2>Examples of operators</h2>

<p>The following can be interpreted as a bare minimum list of operators which an answer should be able to describe.
Here, $\mathbf C$ is an arbitrary set of languages, over an arbitrary finite alphabet $\Sigma$.</p>

<blockquote>
  <p>$\exists \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\\quad \bigl[x \in L \iff \exists c \in \Sigma^{f(|x|)}: (x,c) \in A \bigr] \end{array} \right\}\right.$</p>
</blockquote>

<ul>
<li>The $\exists$ operator was apparently introduced by Wagner&nbsp;[1], albeit with the notation  $\bigvee\! \mathbf C$ rather than $\exists \mathbf C$. The most famous example of a class constructed in this way is $\mathsf{NP} = \exists \mathsf P$. This operator comes with a complementary quantifier $\forall$, in which the $\exists c$ in the definition is replaced by $\forall c$, which allows one to easily define the entire polynomial hierarchy: for instance, $\mathsf{\Sigma_2^P P = \exists \forall P}$. This may possibly be the first operator which was defined.</li>
</ul>

<blockquote>
  <p>$\oplus \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n)) \;\forall x \in \Sigma^\ast: \\ \quad\bigl[x \in L \iff \#\{ c \in \Sigma^{f(|x|)}: (x,c) \in A \} \not\equiv 0 \pmod{2}\bigr]\end{array} \right\}\right.$</p>
</blockquote>

<ul>
<li>The $\oplus$ operator is similar to the $\exists$ operator in that $\oplus\mathbf C$ concerns the number of certificates which exist that are verifiable in the class $\mathbf C$, but instead counts the number of certficiates modulo $2$. This can be used to define the classes $\mathsf{\oplus P}$ and $\mathsf{\oplus L}$. Similar operators "$\mathsf{Mod_k \cdot}$" exist for other moduli $k$.</li>
</ul>

<blockquote>
  <p>$\mathsf{co}\mathbf C := \Bigl\{ L \subseteq \Sigma^\ast \,\Big|\, \exists A \in \mathbf C \;\forall x \in \Sigma^\ast: \bigl[x \in L \iff x \notin A \bigr] \Bigr\}$</p>
</blockquote>

<ul>
<li>This is the complementary operator, and is tacitly used to define $\mathsf{ coNP}$, $\mathsf{coC_=P}$, $\mathsf{coMod_kL}$, and a host of other classes from ones which are not known to be closed under complements.</li>
</ul>

<blockquote>
  <p>$\mathsf{BP}\cdot\mathbf C := \left\{ (\Pi_0, \Pi_1)  \,\left|\, \begin{array}{l} \Pi_0, \Pi_1 \subseteq \Sigma^\ast \;\mathbin\&amp;\; \exists A \in \mathbf C \; \exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\ \quad\left[\begin{array}{l} \bigl(x \in \Pi_0 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \leqslant \tfrac{1}{3} {|\Sigma^{f(|x|)}|} \bigr) \mathbin\&amp; \\ \bigl(x \in \Pi_1 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \geqslant \tfrac{2}{3} {|\Sigma^{f(|x|)}|} \bigr) \end{array}\right]\end{array}\right\}\right.$<br><br>
  &mdash; with apologies for the spacing</p>
</blockquote>

<ul>
<li>The $\mathsf{BP}$ operator was apparently introduced by Sch&ouml;ning&nbsp;[2], albeit to define languages (i.e.&nbsp;he did not permit a probability gap) and without using the explicit constants $\tfrac{1}{3}$ or $\frac{2}{3}$. The definition here yields promise-problems instead, with YES-instances $\Pi_1$ and NO-instances in $\Pi_0$. Note that $\mathsf{BPP = BP\cdot P}$, and $\mathsf{AM = BP\cdot NP}$; this operator was used by Toda and Ogiwara [3] to show that $\mathsf{P^{\#P} \subseteq BP\cdot\oplus P}$.</li>
</ul>

<h2>Remarks</h2>

<p>Other important operators which one can abstract from the definitions of standard classes are $\mathsf{C_= \cdot\mathbf C}$ (from the classes $\mathsf{C_= P}$ and $\mathsf{C_= L}$) and $\mathsf C\cdot\mathbf C$ (from the classes $\mathsf{PP}$ and $\mathsf{PL}$). It is also implicit in most of the literature that $\mathsf{F\cdot}$ (yielding function problems from decision classes) and $\#\cdot$ (yielding counting classes from decision classes) are also complexity operators.</p>

<p>There is an article by Borchert and Silvestri [4] which propose to define an operator for each class, but which does not seem to be referred to much in the literature; I also worry that such a general approach may have subtle definitional issues. They in turn refer to a good presentation by K&ouml;bler, Sch&ouml;ning, and Tor&aacute;n [5], which however is now over 20 years old, and also seems to miss out $\oplus$.</p>

<h2>Question</h2>

<p>What book or article is a good reference for complexity class operators?</p>

<h3>References</h3>

<p>[1]:  K. Wagner, <em>The complexity of combinatorial problems with succinct input representations</em>, Acta Inform. 23 (1986) 325–356.</p>

<p>[2]: U. Sch&ouml;ning, <em>Probabilistic complexity classes and lowness</em>, in Proc. 2nd IEEE Conference on Structure in Complexity Theory, 1987, pp. 2-8; also in J. Comput. System Sci., 39 (1989), pp. 84-100.</p>

<p>[3]: S. Toda and M. Ogiwara, <em>Counting classes are at least as hard as the polynomial-time hierarchy</em>, SIAM J.
Comput. 21 (1992) 316–328.</p>

<p>[4]: B. and Borchert, R.  Silvestri, <em>Dot operators</em>, Theoretical Computer Science
Volume 262 (2001), 501–523.</p>

<p>[5]: J. K&ouml;bler, U. Sch&ouml;ning, and J. Tor&aacute;n, The Graph Isomorphism Problem: Its Structural Complexity, Birkh&auml;user, Basel (1993).</p>

CC BY-SA 3.0
2014-03-18T14:09:31.160Z
A noteworthy predecessor to the notion of a complexity operator is the treatment of 
[6]: S. Zachos, [*Probabilistic Quantifiers, Adversaries, and Complexity Classes: An Overview,*](http://link.springer.com/chapter/10.1007%2F3-540-16486-3_112) Proc. of the Conference on Structure in Complexity Theory (pp.383--400), Berkeley, California, 1986, which is cited by Schöning [2] above in connection with $\mathsf{BP\cdot NP}$.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-18T17:28:57.627Z
Again by Zachos, this might help too: [Combinatory Complexity: Operators on Complexity Classes](http://www.cs.ucy.ac.cy/conferences/pls4/Pagourtzis.ps)
Alessandro Cosentino
CC BY-SA 3.0
2014-03-18T17:31:35.370Z
@NieldeBeaudrap Zachos is the one that first came up with the notion of complexity class operators. I recall from his lectures that he explicitly stated this. There is also one for overwhelming majority, ${\exists^+}$.
Tayfun Pay
CC BY-SA 3.0
2014-03-18T17:44:10.690Z
@TayfunPay: indeed, the quantifier $\exists^+$ is useful for describing $\mathsf{BP\cdot}$, albeit using the two-sided formalism described in [6] (in my comment above) rather than the way described by Schöning.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-18T17:49:42.667Z
@NieldeBeaudrap There is also another one that can be used to define unbounded two-sided error ${\exists _{1/2}}$.
Tayfun Pay
CC BY-SA 3.0
2014-03-19T01:23:12.893Z
the field seems to be waiting for a std ref/handbook on this subj, unifying notation/formalism. also wouldnt you consider $A^B$ relativization and "augmented with advice" eg as in "P/poly" also as "operators"? the Aaronson [complexity zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo) does cover some of this.
vzn
CC BY-SA 3.0
2014-03-19T01:44:54.297Z
@vzn: I'm not considering "variations on" extablished complexity classes: I'm considering maps from complexity classes to complexity classes. A recent question illustrates exactly why [relativization is not an operator on classes](http://cstheory.stackexchange.com/q/21590/248). On the other hand, it seems that $\mathsf{\ast/poly}$ actually is an operator on classes: it is a simple exercise to show this. However, for the sake of this question, I don't care about $\mathsf{\ast/poly}$ as an operator: what I want is a good expository article to cite, which includes the named examples.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-20T18:05:25.777Z
@NieldeBeaudrap: I made it as an answer, but please wait before accepting it, I would like to see a better reference.
Alessandro Cosentino
CC BY-SA 3.0
2014-03-20T18:19:20.330Z
@AlessandroCosentino: Sure, I'll wait. I'd like to edit it later to state what results it does describe if you don't mind; or you can if you like. I will at least wait to accept after that.
Niel de Beaudrap
CC BY-SA 3.0
2014-03-20T18:28:17.037Z
@NieldeBeaudrap: feel free to edit it as much as you want.
Alessandro Cosentino
<reference-request><complexity-classes>
A good reference for complexity class operators?
Niel de Beaudrap
# A good reference for complexity class operators?

(Asked by: username_0 on 2014-03-18)

I'm interested if there exist any good expository articles or surveys to which I can refer when I write about *complexity class operators*: operators which transform complexity classes by doing things such as adding quantifiers to them.

## Examples of operators

The following can be interpreted as a bare minimum list of operators which an answer should be able to describe.
Here, $\mathbf C$ is an arbitrary set of languages, over an arbitrary finite alphabet $\Sigma$.

> $\exists \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\\quad \bigl[x \in L \iff \exists c \in \Sigma^{f(|x|)}: (x,c) \in A \bigr] \end{array} \right\}\right.$

* The $\exists$ operator was apparently introduced by Wagner [1], albeit with the notation $\bigvee\! \mathbf C$ rather than $\exists \mathbf C$. The most famous example of a class constructed in this way is $\mathsf{NP} = \exists \mathsf P$. This operator comes with a complementary quantifier $\forall$, in which the $\exists c$ in the definition is replaced by $\forall c$, which allows one to easily define the entire polynomial hierarchy: for instance, $\mathsf{\Sigma\_2^P P = \exists \forall P}$. This may possibly be the first operator which was defined.

> $\oplus \mathbf C := \left\{ L \subseteq \Sigma^\ast \,\left|\, \begin{array}{l} \exists A \in \mathbf C \;\exists f \in O(\mathrm{poly}(n)) \;\forall x \in \Sigma^\ast: \\ \quad\bigl[x \in L \iff \#\{ c \in \Sigma^{f(|x|)}: (x,c) \in A \} \not\equiv 0 \pmod{2}\bigr]\end{array} \right\}\right.$

* The $\oplus$ operator is similar to the $\exists$ operator in that $\oplus\mathbf C$ concerns the number of certificates which exist that are verifiable in the class $\mathbf C$, but instead counts the number of certficiates modulo $2$. This can be used to define the classes $\mathsf{\oplus P}$ and $\mathsf{\oplus L}$. Similar operators "$\mathsf{Mod\_k \cdot}$" exist for other moduli $k$.

> $\mathsf{co}\mathbf C := \Bigl\{ L \subseteq \Sigma^\ast \,\Big|\, \exists A \in \mathbf C \;\forall x \in \Sigma^\ast: \bigl[x \in L \iff x \notin A \bigr] \Bigr\}$

* This is the complementary operator, and is tacitly used to define $\mathsf{ coNP}$, $\mathsf{coC\_=P}$, $\mathsf{coMod\_kL}$, and a host of other classes from ones which are not known to be closed under complements.

> $\mathsf{BP}\cdot\mathbf C := \left\{ (\Pi\_0, \Pi\_1) \,\left|\, \begin{array}{l} \Pi\_0, \Pi\_1 \subseteq \Sigma^\ast \;\mathbin\&\; \exists A \in \mathbf C \; \exists f \in O(\mathrm{poly}(n))\;\forall x \in \Sigma^\ast: \\ \quad\left[\begin{array}{l} \bigl(x \in \Pi\_0 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \leqslant \tfrac{1}{3} {|\Sigma^{f(|x|)}|} \bigr) \mathbin\& \\ \bigl(x \in \Pi\_1 \Leftrightarrow \#\{c \in \Sigma^{f(|x|)}: (x,c) \in A \} \geqslant \tfrac{2}{3} {|\Sigma^{f(|x|)}|} \bigr) \end{array}\right]\end{array}\right\}\right.$  
>   
> — with apologies for the spacing

* The $\mathsf{BP}$ operator was apparently introduced by Schöning [2], albeit to define languages (i.e. he did not permit a probability gap) and without using the explicit constants $\tfrac{1}{3}$ or $\frac{2}{3}$. The definition here yields promise-problems instead, with YES-instances $\Pi\_1$ and NO-instances in $\Pi\_0$. Note that $\mathsf{BPP = BP\cdot P}$, and $\mathsf{AM = BP\cdot NP}$; this operator was used by Toda and Ogiwara [3] to show that $\mathsf{P^{\#P} \subseteq BP\cdot\oplus P}$.

## Remarks

Other important operators which one can abstract from the definitions of standard classes are $\mathsf{C\_= \cdot\mathbf C}$ (from the classes $\mathsf{C\_= P}$ and $\mathsf{C\_= L}$) and $\mathsf C\cdot\mathbf C$ (from the classes $\mathsf{PP}$ and $\mathsf{PL}$). It is also implicit in most of the literature that $\mathsf{F\cdot}$ (yielding function problems from decision classes) and $\#\cdot$ (yielding counting classes from decision classes) are also complexity operators.

There is an article by Borchert and Silvestri [4] which propose to define an operator for each class, but which does not seem to be referred to much in the literature; I also worry that such a general approach may have subtle definitional issues. They in turn refer to a good presentation by Köbler, Schöning, and Torán [5], which however is now over 20 years old, and also seems to miss out $\oplus$.

## Question

What book or article is a good reference for complexity class operators?

### References

[1]: K. Wagner, *The complexity of combinatorial problems with succinct input representations*, Acta Inform. 23 (1986) 325–356.

[2]: U. Schöning, *Probabilistic complexity classes and lowness*, in Proc. 2nd IEEE Conference on Structure in Complexity Theory, 1987, pp. 2-8; also in J. Comput. System Sci., 39 (1989), pp. 84-100.

[3]: S. Toda and M. Ogiwara, *Counting classes are at least as hard as the polynomial-time hierarchy*, SIAM J.
Comput. 21 (1992) 316–328.

[4]: B. and Borchert, R. Silvestri, *Dot operators*, Theoretical Computer Science
Volume 262 (2001), 501–523.

[5]: J. Köbler, U. Schöning, and J. Torán, The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, Basel (1993).

**Tags:** reference-request, complexity-classes
> **Comments:**
> **username_0**: A noteworthy predecessor to the notion of a complexity operator is the treatment of  [6]: S. Zachos, [*Probabilistic Quantifiers, Adversaries, and Complexity Classes: An Overview,*](http://link.springer.com/chapter/10.1007%2F3-540-16486-3_112) Proc. of the Conference on Structure in Complexity Theory (pp.383--400), Berkeley, California, 1986, which is cited by Schöning [2] above in connection with $\mathsf{BP\cdot NP}$.  
> **username_1**: Again by Zachos, this might help too: [Combinatory Complexity: Operators on Complexity Classes](http://www.cs.ucy.ac.cy/conferences/pls4/Pagourtzis.ps)  
> **username_2**: @NieldeBeaudrap Zachos is the one that first came up with the notion of complexity class operators. I recall from his lectures that he explicitly stated this. There is also one for overwhelming majority, ${\exists^+}$.  
> **username_0**: @TayfunPay: indeed, the quantifier $\exists^+$ is useful for describing $\mathsf{BP\cdot}$, albeit using the two-sided formalism described in [6] (in my comment above) rather than the way described by Schöning.  
> **username_2**: @NieldeBeaudrap There is also another one that can be used to define unbounded two-sided error ${\exists _{1/2}}$.  
> **username_3**: the field seems to be waiting for a std ref/handbook on this subj, unifying notation/formalism. also wouldnt you consider $A^B$ relativization and "augmented with advice" eg as in "P/poly" also as "operators"? the Aaronson [complexity zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo) does cover some of this.  
> **username_0**: @vzn: I'm not considering "variations on" extablished complexity classes: I'm considering maps from complexity classes to complexity classes. A recent question illustrates exactly why [relativization is not an operator on classes](http://cstheory.stackexchange.com/q/21590/248). On the other hand, it seems that $\mathsf{\ast/poly}$ actually is an operator on classes: it is a simple exercise to show this. However, for the sake of this question, I don't care about $\mathsf{\ast/poly}$ as an operator: what I want is a good expository article to cite, which includes the named examples.  
> **username_1**: @NieldeBeaudrap: I made it as an answer, but please wait before accepting it, I would like to see a better reference.  
> **username_0**: @AlessandroCosentino: Sure, I'll wait. I'd like to edit it later to state what results it does describe if you don't mind; or you can if you like. I will at least wait to accept after that.  
> **username_1**: @NieldeBeaudrap: feel free to edit it as much as you want.  

---

## 2 answers

### Answer by username_1 on 2014-03-20. Score: 19 | Accepted answer

Here is a reference with many definitions of operators (not many details though):

> S. Zachos and A. Pagourtzis,
> [Combinatory Complexity: Operators on Complexity Classes](http://www.cs.ucy.ac.cy/conferences/pls4/Pagourtzis.ps), Proceedings of 4th Panhellenic Logic Symposium (PLS 2003), Thessaloniki, Jul 7-10 2003.

* It defines an identity operator $\mathcal E$, as well as operators $\mathsf{co}$- , $\mathsf{N}$ (corresponding to $\exists$ above), $\mathsf{BP}$, $\mathsf{R}$ (corresponding to bounded one-sided error), $\oplus$, $\mathsf U$ (corresponding to non-determinism with a unique accepting transition), $\mathsf P$ (corresponding to unbounded two-sided error), and $\Delta$ (which for a class $\mathbf C$ forms $\mathbf C \cap \mathsf{co}\mathbf C$).
* It shows that:

  1. $\mathcal E$ is an identity element with respect to composition [Definition 1];
  2. $\mathsf{co}$- is self-inverse [Definition 2];
  3. $\mathsf{N}$ is idempotent [Definition 3] — implicit is that $\mathsf{BP}$, $\mathsf{R}$, $\oplus$, $\mathsf U$, and $\mathsf{P}$ are also idempotent;
  4. $\mathsf{BP}$ and $\mathsf{P}$ commute with $\mathsf{co}$-  [Definitions 4 and 8], while $\oplus$ is invariant under right-composition with $\mathsf{co}$- [Definition 6];
  5. The above operators are all monotone (that is, ${\mathbf C\_1 \subseteq \mathbf C\_2} \implies {\mathcal O\cdot\mathbf C\_1 \subseteq \mathcal O\cdot\mathbf C\_2}$ for all operators $\mathcal O$ above):

Throughout, it also describes a handful of ways that these operators relate to traditional complexity classes, such as $\mathsf{\Sigma^p\_2 P}$, $\mathsf{ZPP}$, $\mathsf{AM}$, $\mathsf{MA}$, etc.


---

### Answer by username_0 on 2014-03-18. Score: 18

As an introductory reference to the notion of a complexity operator (and demonstrating some applications of the idea), the best I have found so far is

> D. Kozen, Theory of Computation (Springer 2006)

which is derived from lecture notes on computational complexity and related topics. On page 187 ("Supplementary Lecture G: Toda's Theorem"), he defines the operators

* $\mathsf R$ (for random certificates with bounded one-sided error, as in the class $\mathsf{RP}$)
* $\mathsf{BP}$ (for random certificates with bounded two-sided error, see above)
* $\mathsf P$ (for random certificates with unbounded error, c.f. $\mathsf C$ in the remarks above)
* $\oplus$ (for an odd number of certificates, see above)
* $\Sigma^{\mathrm{p}}$ (for existence of polynomial-length certificates, c.f. $\exists$ above)
* $\Sigma^{\mathrm{log}}$ (for existence of $O(\log n)$-length certificates, c.f. $\exists$ above)
* $\Pi^{\mathrm{p}}$ and $\Pi^{\mathrm{log}}$ (complementary operators to $\Sigma^{\mathrm{p}}$ and $\Sigma^{\mathrm{log}}$: see remarks on $\forall$ above)
* $\#$ (defining a counting class, c.f. remarks above)

and tacitly defines $\mathsf{co\text-}$ on page 12 in the usual way.

Kozen's treatment of these operators is enough to indicate how they are connected with the "usual" complexity classes, and to describe Toda's theorem, but does not much discuss their relationships and only mentions them for a total of 6 pages (in what is after all a book covering a much wider topic).
Hopefully someone can provide a better reference than this.


---

