<p>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.</p>

CC BY-SA 2.5
2010-09-05T05:03:56.157Z
2010-09-05T05:03:56.157Z
Marcos Villagra
<p>${\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.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-05T08:45:03.730Z
Sorry, I didn't get it. Can you explain a bit more?
Sadeq Dousti
CC BY-SA 2.5
2010-09-06T03:18:18.617Z
I hope the editing make more sens
Arthur MILCHIOR
CC BY-SA 2.5
2010-09-06T08:39:41.817Z
Very well, thank you. That makes a lot of sense.
Sadeq Dousti
CC BY-SA 2.5
2010-09-05T02:29:28.360Z
2010-09-06T03:18:06.323Z
2010-09-06T03:18:06.323Z
Arthur MILCHIOR
<p>In the "last paragraph" of the "first page" of the following paper:</p>

<p><a href="http://dx.doi.org/10.1016/0304-3975(95)91133-B" rel="noreferrer"><strong>Vikraman Arvind</strong>, <strong>Johannes Köbler</strong>, <strong>Uwe Schöning</strong>, <strong>Rainer Schuler</strong>, "If NP Has Polynomial-Size Circuits, then MA = AM," Theoretical Computer Science, 1995.</a></p>

<p>I encountered a somewhat counter-intuitive claim: </p>

<p>$(\Sigma^P_2 \cap \Pi^P_2)^{NP} = \Sigma^P_3 \cap \Pi^P_3$</p>

<p>I think the identity above is deduced from the following:</p>

<p>$(\Sigma^P_2)^{NP} = \Sigma^P_3$</p>

<p>and</p>

<p>$(\Pi^P_2)^{NP} = \Pi^P_3$</p>

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

<p><strong>Edit:</strong> In light of Kristoffer's comment below, I'd like to add the following inspiring remark from <a href="http://rads.stackoverflow.com/amzn/click/052188473X" rel="noreferrer">Goldreich's complexity book</a> (pp. 118-119):</p>

<blockquote>
  <p>It should be clear that the class $C_1^{C_2}$ can be defined for two complexity classes $C_1$ and $C_2$, <em>provided that $C_1$ is associated with a class of standard machines that generalizes naturally to a class of oracle machines.</em> 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$.</p>
</blockquote>

CC BY-SA 2.5
2010-09-05T01:53:44.270Z
But… isn’t $(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$ the same as $\mathbf{NP}^{\mathbf{NP}}$? Or am I missing something here?
Antonio E. Porreca
CC BY-SA 2.5
2010-09-05T08:43:26.273Z
I don't think we can judge that easily. Otherwise, one can deduce that $\mathbf{NP}^\mathbf{NP}$ is the same as $\mathbf{NP}$!
Sadeq Dousti
CC BY-SA 2.5
2010-09-05T09:52:52.587Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2010-09-05T10:13:19.493Z
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.
Antonio E. Porreca
CC BY-SA 2.5
2010-09-05T10:38:48.977Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 2.5
2010-09-06T08:30:40.400Z
Sadeq: Nobody is claiming the statement in the paper is wrong.
Kristoffer Arnsfelt Hansen
<cc.complexity-theory><complexity-classes>
Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?
Sadeq Dousti
# Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$?

(Asked by: username_0 on 2010-09-05)

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.](http://dx.doi.org/10.1016/0304-3975(95)91133-B)

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!

**Edit:** In light of Kristoffer's comment below, I'd like to add the following inspiring remark from [Goldreich's complexity book](http://rads.stackoverflow.com/amzn/click/052188473X) (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$.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: But… isn’t $(\mathbf{NP}^{\mathbf{NP}})^{\mathbf{NP}}$ the same as $\mathbf{NP}^{\mathbf{NP}}$? Or am I missing something here?  
> **username_0**: I don't think we can judge that easily. Otherwise, one can deduce that $\mathbf{NP}^\mathbf{NP}$ is the same as $\mathbf{NP}$!  
> **username_2**: 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.  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_2**: Sadeq: Nobody is claiming the statement in the paper is wrong.  

---

## 2 answers

### Answer by username_4 on 2010-09-05. Score: 13 | Accepted answer

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

> **Comments:**
> **username_0**: Sorry, I didn't get it. Can you explain a bit more?  
> **username_4**: I hope the editing make more sens  
> **username_0**: Very well, thank you. That makes a lot of sense.  

---

### Answer by username_3 on 2010-09-05. Score: 4

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.


---

