Complexity classes where $C^C = C$

Question

One possible motivation for studying computational complexity classes is to understand the power of different kinds of computational resources (randomness, non-determinism, quantum effects, etc.). If we look at it from this perspective, then it seems like we can obtain one plausible axiom for any attempt at characterizing which computations are feasible in some model:

• Any feasible computation can always invoke another feasible computation as a subroutine. In other words, suppose the programs $P,Q$ are considered feasible to execute. Then if we construct a new program by hooking $P$ and $Q$ up, so that $P$ makes subroutine calls to $Q$, then this new program is also feasible.

Translated into the language of complexity classes, this axiom amounts to the following requirement:

• If $C$ is a complexity class intended to capture which computations are feasible in some model, then we must have $C^C = C$.

(Here $C^C$ represents computations in $C$ that can invoke an oracle from $C$; that's an oracle complexity class.) So, let's call a complexity class $C$ plausible if it satisfies $C^C=C$.

My question: What complexity classes do we know of, that are plausible (by this definition of plausible)?

For instance, $P$ is plausible, since $P^P=P$. Do we have $BPP^{BPP} = BPP$? What about $BQP^{BQP} = BQP$? What are some other complexity classes that meet this criterion?

I suspect that $NP^{NP} \ne NP$ (or at least, that would be our best guess, even if we cannot prove it). Is there a complexity class that captures non-deterministic computation and that is plausible, under this definition? If we let $C$ denote the smallest complexity class such that $NP \subseteq C$ and $C^C \subseteq C$, is there any clean characterization of this $C$?

Answer 1

$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$ has been proved in Strengths and Weaknesses of Quantum Computing Bennett et al. (arXiv).

According to the complexity zoo, $\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$.

Answer 2

Here are some answers to some of the questions, but certainly not all of them:

Apparently, according to Wikipedia, we have $P^P=P$, $BPP^{BPP}=BPP$, $PSPACE^{PSPACE}=PSPACE$, $L^L=L$, and $\oplus P^{\oplus P} = \oplus P$. See also What is complexity class $\oplus P^{\oplus P}$, which observes that $\oplus P^{\oplus P} = \oplus P$.

Also, if $C^C=C$, then $C$ is closed under complement. Thus it is unlikely that $NP^{NP}=NP$: this would imply that $NP=\textit{co-}NP$, which seems unlikely. It looks like the smallest plausible complexity class that contains $NP$ is $PH$ (see Wikipedia).

I don't know what the situation is with $BQP$. I don't know whether there are other interesting examples of plausible complexity classes.

Answer 3

A complexity class $ C $ is called self-low precisely when $ C^C = C $. In general, "lowness" was studied a lot in the 80s and 90s -- google will uncover much for you.

Answer 4

This comment lists L (logspace), NC (polylog depth), P, BPP, BQP, and PSPACE as examples of self-low complexity classes.