Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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}}$ ?

share|improve this question
3  
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 Sep 5 '10 at 1:53
3  
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 Sep 5 '10 at 9:52
2  
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 Sep 5 '10 at 10:13
1  
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 Sep 5 '10 at 10:38
1  
Sadeq: Nobody is claiming the statement in the paper is wrong. –  Kristoffer Arnsfelt Hansen Sep 6 '10 at 8:30

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
1  
Sorry, I didn't get it. Can you explain a bit more? –  Sadeq Dousti Sep 5 '10 at 8:45
    
I hope the editing make more sens –  Arthur MILCHIOR Sep 6 '10 at 3:18
    
Very well, thank you. That makes a lot of sense. –  Sadeq Dousti Sep 6 '10 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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