Classes de complexité où

Une motivation possible pour étudier les classes de complexité de calcul est de comprendre la puissance de différents types de ressources de calcul (caractère aléatoire, non-déterminisme, effets quantiques, etc.). Si nous le regardons sous cet angle, il semble que nous pouvons obtenir un axiome plausible pour toute tentative de caractériser les calculs réalisables dans un modèle:

• Tout calcul réalisable peut toujours invoquer un autre calcul réalisable comme sous-programme. En d'autres termes, supposons que les programmes sont considérés comme réalisables. Ensuite, si nous construisons un nouveau programme en raccordant et , de sorte que fasse des appels de sous-programme à , alors ce nouveau programme est également réalisable.$P,Q$$P$$Q$$P$$Q$

Traduit dans le langage des classes de complexité, cet axiome revient à l'exigence suivante:

• Si est une classe de complexité destinée à la capture qui calculs sont réalisables dans certains modèles, nous devons avoir .$C$$C^C = C$

(Ici représente les calculs en qui peut invoquer un oracle de ,. Qui est une classe de complexité oracle) Donc, nous allons appeler une classe de complexité plausible si elle satisfait .$C^C$$C$$C$$C$ $C^C=C$

Ma question: de quelles classes de complexité connaissons-nous, qui sont plausibles (par cette définition de plausible)?

Par exemple, est plausible, puisque . Avons-nous ? Qu'en est-il de ? Quelles sont les autres classes de complexité qui répondent à ce critère?$P$$P^P=P$$BPP^{BPP} = BPP$$BQP^{BQP} = BQP$

Je soupçonne que (ou du moins, ce serait notre meilleure estimation, même si nous ne pouvons pas le prouver). Existe-t-il une classe de complexité qui capture le calcul non déterministe et qui est plausible, selon cette définition? Si nous laissons désigner la plus petite classe de complexité telle que et , existe-t-il une caractérisation nette de ce ?C N P ⊆ C C C ⊆ C $NP^{NP} \ne NP$$C$$NP \subseteq C$$C^C \subseteq C$$C$

a été prouvé dansForces et faiblesses de l'informatique quantiqueBennett et al. (arXiv).$\mathrm{BQP}^{\mathrm{BQP}} = \mathrm{BQP}$

Selon la complexité de zoo, .$\mathrm{ZBQP}^{\mathrm{ZBQP}} = \mathrm{ZBQP}$

Voici quelques réponses à certaines des questions, mais certainement pas toutes:

Apparemment, selon Wikipedia , nous avons , 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 ,$P^P=P$$BPP^{BPP}=BPP$$PSPACE^{PSPACE}=PSPACE$ , et ⊕ P ⊕ P = ⊕ P . Voir aussiQu'est-ce que la classe de complexité ⊕ P$L^L=L$$\oplus P^{\oplus P} = \oplus P$$\oplus P^{\oplus P}$ , qui observe que.$\oplus P^{\oplus P} = \oplus P$

De plus, si , alors C est fermé sous complément. Il est donc peu probable que N P N P = N P : cela impliquerait que $C^C=C$$C$$NP^{NP}=NP$ , ce qui semble peu probable. Il ressemble à la plus petite classe de complexité plausible qui contient N P est P H (voirWikipedia).$NP=\textit{co-}NP$$NP$$PH$

Je ne sais pas quelle est la situation avec . Je ne sais pas s'il existe d'autres exemples intéressants de classes de complexité plausibles.$BQP$

Une classe de complexité est appelée self-low précisément lorsque$C$ . En général, la "lowness" a été beaucoup étudiée dans les années 80 et 90 - Google en découvrira beaucoup pour vous.$C^C = C$

Ce commentaire répertorie L (espace de journal), NC (profondeur de polylog), P, BPP, BQP et PSPACE comme exemples de classes à faible complexité.