Komplexitätsklassen mit

Eine mögliche Motivation für das Studium von Computerkomplexitätsklassen besteht darin, die Leistungsfähigkeit verschiedener Arten von Computerressourcen (Zufälligkeit, Nichtdeterminismus, Quanteneffekte usw.) zu verstehen. Wenn wir es aus dieser Perspektive betrachten, dann scheint es, als könnten wir ein plausibles Axiom für jeden Versuch erhalten, zu charakterisieren, welche Berechnungen in einem Modell möglich sind:

• Jede mögliche Berechnung kann immer eine andere mögliche Berechnung als Subroutine aufrufen. Mit anderen Worten, es sei angenommen, dass die Programme $P,Q$ ausführbar sind. Wenn wir dann ein neues Programm durch Verknüpfen von $P$ und $Q$ aufbauen, so dass $P$ Unterprogrammaufrufe für $Q$ , ist dieses neue Programm ebenfalls möglich.

Übersetzt in die Sprache der Komplexitätsklassen ergibt sich für dieses Axiom folgende Anforderung:

• Wenn eine Komplexitätsklasse ist, die erfassen soll, welche Berechnungen in einem Modell möglich sind, muss C C = C sein .$C$$C^C = C$

(Hier stellt Berechnungen in C dar , die ein Orakel aus C aufrufen können ; das ist eine Orakelkomplexitätsklasse.) Nennen wir also eine Komplexitätsklasse C plausibel, wenn sie C C = C erfüllt .$C^C$$C$$C$$C$ $C^C=C$

Meine Frage: Welche Komplexitätsklassen kennen wir, die plausibel sind (nach dieser Definition von plausibel)?

Zum Beispiel ist plausibel, da P P = P . Haben wir B P P B P P = B P P ? Was ist mit B Q P B Q P = B Q P ? Welche anderen Komplexitätsklassen erfüllen dieses Kriterium?$P$$P^P=P$$BPP^{BPP} = BPP$$BQP^{BQP} = BQP$

Ich vermute, dass (oder zumindest, das wäre unsere beste Vermutung, auch wenn wir es nicht beweisen können). Gibt es eine Komplexitätsklasse, die nicht deterministische Berechnungen erfasst und die unter dieser Definition plausibel ist? Wenn wir C die kleinste Komplexitätsklasse bezeichnen lassen, so dass N P ⊆ C und C C ⊆ C , gibt es eine saubere Charakterisierung dieses C ?$NP^{NP} \ne NP$$C$$NP \subseteq C$$C^C \subseteq C$$C$

wurde inStärken und Schwächen von Quantum Computing nachgewiesenBennett et al. (arXiv).$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$

Entsprechend der Komplexität Zoo, .$\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$

Hier sind einige Antworten auf einige der Fragen, aber sicherlich nicht alle:

Offenbar nach Wikipedia , haben wir , B P P B P P = B P P , P S P A C E P S P A C E = P S P A C E , L L = L , und ⊕ P ⊕ P = ⊕ P . Siehe auch Was Komplexitätsklasse ist & xoplus; & xoplus;$P^P=P$$BPP^{BPP}=BPP$$PSPACE^{PSPACE}=PSPACE$$L^L=L$$\oplus P^{\oplus P} = \oplus P$$\oplus P^{\oplus P}$ , die beobachtetdass.$\oplus P^{\oplus P} = \oplus P$

Auch wenn , dann C unter Ergänzung geschlossen. Somit ist es unwahrscheinlich , dass N P N P = N P : Dies würde bedeuten , dass N P = Co- N P , was unwahrscheinlich scheint. Es sieht aus wie die kleinste plausible Komplexitätsklasse , die enthält N P ist P H (siehe Wikipedia ).$C^C=C$$C$$NP^{NP}=NP$$NP=\textit{co-}NP$$NP$$PH$

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

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.

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