Est-ce que

Dans le "dernier paragraphe" de la "première page" de l'article suivant:

Vikraman Arvind , Johannes Köbler , Uwe Schöning , Rainer Schuler , «If NP Has Polynomial-Size Circuits, then MA = AM», Theoretical Computer Science, 1995.

J'ai rencontré une affirmation quelque peu contre-intuitive:

$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$

Je pense que l'identité ci-dessus est déduite des éléments suivants:

$(\Sigma^P_2)^{NP} = \Sigma^P_3$

et

$(\Pi^P_2)^{NP} = \Pi^P_3$

Le premier est plus simplement écrit comme , ce qui est assez étrange!$(NP^{NP})^{NP} = NP^{NP^{NP}}$

Edit: À la lumière du commentaire de Kristoffer ci-dessous, je voudrais ajouter la remarque inspirante suivante du livre sur la complexité de Goldreich (pp. 118-119):

Il doit être clair que la classe peut être définie pour deux classes de complexité C 1 et C 2 , à condition que C 1 soit associé à une classe de machines standard qui se généralise naturellement à une classe de machines oracle. En fait, la classe C C 2 1 n'est pas définie sur la base de la classe C 1 mais plutôt par analogie avec elle. Plus précisément, supposons que C $C_1^{C_2}$$C_1$$C_2$$C_1$$C_1^{C_2}$$C_1$$C_1$est la classe d'ensembles qui sont reconnaissables (ou plutôt acceptés) par des machines d'un certain type (par exemple, déterministes ou non déterministes) avec certaines limites de ressources (par exemple, les limites de temps et / ou d'espace). Ensuite, nous considérons des machines oracle analogues (c'est-à-dire du même type et avec les mêmes limites de ressources), et disons que s'il existe une machine oracle adéquate M 1 (c'est-à-dire de ce type et des limites de ressources) et un ensemble S 2 ∈ C 2 de telle sorte que M S 2 1 accepte l'ensemble S .$S \in C_1^{C_2}$$M_1$$S_2 \in C_2$$M_1^{S_2}$$S$

${\Sigma_2^P}^{NP}$

$(NP^{NP})^{A}$$(NP^{NP^A\cup A})$$\cup$$A$$NP^A$

${\Sigma_2^P}^{NP}$$(NP^{(NP^{NP})})^{NP}$$(NP^{NP^{NP}})$$NP$$NP^{NP}$ oracle.

From Arora and Barak (p. 102) theorem 5.12: "For every $i\geq 2$, $\sum_i^p=NP^{\sum_{i-1}SAT}$". Remember that $\sum_{i}SAT$ is the QBF formula with $i$ alternations which is complete for $\sum_i^p$. Then $\sum_2^p=NP^{SAT}$ and given that SAT is NP-complete you just write $\sum_2^p=NP^{NP}$, so far so good. Extending this notation to $i=3$ you get $NP^{NP^{NP}}$, but the last two "NPs" are just an oracle for the language $\sum_{2}SAT$ with at most 2 alternations. It seems to me that its just a shorthand notation for oracle access.