21
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ See this, this and this on Theoretical Computer Science -- you need to be careful. $\endgroup$ – András Salamon Aug 22 '13 at 21:43
  • $\begingroup$ OK, @AndrásSalamon, thank you for the warning and the references! Can you help me identify how to formulate my problem with appropriate caution? Do you have any suggestions? Or, if the answer depends upon the formulation, can you explain what answer we'd get with different formulations? $\endgroup$ – D.W. Aug 23 '13 at 0:08
  • $\begingroup$ Constant^Constant = Constant. $\endgroup$ – Joshua Sep 25 '15 at 1:20
13
$\begingroup$

$\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}$.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ If $NP^{NP} = NP$ then the polynomial hierarchy collapses at level 1, i.e. $\Sigma_2^P = NP$. This is not generally believed to be the case (but this is an open problem). If $NP \subseteq C$ and $C^C \subseteq C$, then $NP^{NP} \subseteq C$ and by induction $C$ contains the polynomial hierarchy. $\endgroup$ – András Salamon Aug 24 '13 at 9:27
6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Can you give some examples? $\endgroup$ – Ryan Mar 17 '15 at 17:55
  • $\begingroup$ There are examples among the other answers above: P, BPP, etc. $\endgroup$ – Ryan Williams Mar 17 '15 at 18:23
  • 1
    $\begingroup$ Right but have you been able to find any that haven't been mentioned before? $\endgroup$ – Ryan Mar 17 '15 at 18:35
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.