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

Vikraman Arvind, 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$


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

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

Edit: In light of Kristoffer's comment below, I'd like to add the following inspiring remark from Goldreich's complexity book (pp. 118-119):

It should be clear that the class $C_1^{C_2}$ can be defined for two complexity classes $C_1$ and $C_2$, provided that $C_1$ is associated with a class of standard machines that generalizes naturally to a class of oracle machines. Actually, the class $C_1^{C_2}$ is not defined based on the class $C_1$ but rather by analogy to it. Specifically, suppose that $C_1$ is the class of sets that are recognizable (or rather accepted) by machines of a certain type (e.g., deterministic or non-deterministic) with certain resource bounds (e.g., time and/or space bounds). Then, we consider analogous oracle machines (i.e., of the same type and with the same resource bounds), and say that $S \in C_1^{C_2}$ if there exists an adequate oracle machine $M_1$ (i.e., of this type and resource bounds) and a set $S_2 \in C_2$ such that $M_1^{S_2}$ accepts the set $S$.

  • 4
    $\begingroup$ But… isn’t $(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$ the same as $\mathbf{NP}^{\mathbf{NP}}$? Or am I missing something here? $\endgroup$ Commented Sep 5, 2010 at 1:53
  • 5
    $\begingroup$ Beware of the dangers of the oracle notation. We have not defined the notion of attaching oracles to any class of languages. Only to classes of languages defined by a computational model where oracles can be attached. Thus in a sense $(NP^{NP})^{NP}$ is not immediately well-defined. $\endgroup$ Commented Sep 5, 2010 at 9:52
  • 2
    $\begingroup$ Well, I agree that the usual notion of “putting $\mathbf{NP}$ as the exponent of a class” is, in general, ill-defined. But the underlying computing model of $\mathbf{NP}^{\mathbf{NP}}$ is well-defined (a polytime NTM with an oracle for some $\mathbf{NP}$-complete problem) and adding another oracle to it, as in $(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$, seems straightforward to me. My point, assuming this interpretation, was that the second oracle is redundant. I’d be glad to know if the symbol $(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$ admits other interpretations. $\endgroup$ Commented Sep 5, 2010 at 10:13
  • 1
    $\begingroup$ That right, under that interpretation the class would not change. However this is not the correct interpretation for relativizing Lautemans's proof, as done in the paper mentioned in the question. $\endgroup$ Commented Sep 5, 2010 at 10:38
  • 1
    $\begingroup$ Sadeq: Nobody is claiming the statement in the paper is wrong. $\endgroup$ Commented Sep 6, 2010 at 8:30

2 Answers 2


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

  • 1
    $\begingroup$ Sorry, I didn't get it. Can you explain a bit more? $\endgroup$ Commented Sep 5, 2010 at 8:45
  • $\begingroup$ I hope the editing make more sens $\endgroup$ Commented Sep 6, 2010 at 3:18
  • $\begingroup$ Very well, thank you. That makes a lot of sense. $\endgroup$ Commented Sep 6, 2010 at 8:39

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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