Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$ ?

Question

In the "last paragraph" of the "first page" of the following paper:

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

I encountered a somewhat counter-intuitive claim:

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

I think the identity above is deduced from the following:

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

and

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

The former is more simply written as $(NP^{NP})^{NP} = NP^{NP^{NP}}$, which is quite odd!

Is it true? Regarding the fame of the authors, I think that must be the case. However, can anybody prove (or disprove) that $(NP^{NP})^{NP} = NP^{NP^{NP}}$ ?

Answer 1

${\Sigma_2^P}^{NP}$ is the set of language decided by an alternating turing machine in existential, and then universal state, with an oracle in NP. Both the universal and the existantial part can querye NP.

Hence, in this case you decided to write this as $(NP^{NP})^{A}$ then the way you should think of it is as $(NP^{NP^A\cup A})$ (by $\cup$ I mean an oracle either to $A$ or to an $NP^A$ language).

Hence ${\Sigma_2^P}^{NP}$ is equal to $(NP^{(NP^{NP})})^{NP}$ which is certainly equal to $(NP^{NP^{NP}})$ since every query you could make to the $NP$ oracle, you could make it to the $NP^{NP}$ oracle.

Answer 2

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.