# Does $NP^{NP}=NP$?

Is $NP$ with oracle access to $NP$ larger than just $NP$? As I understand $NP^ {NP}$ is just a turing machine that can make queries to an other $NP$ machine if so than $NP$ can simulate $NP^{NP}$? Is there something wrong with this argument?

## migrated from cstheory.stackexchange.comJul 12 '12 at 19:21

This question came from our site for theoretical computer scientists and researchers in related fields.

• The answer is we don't know, and the fact that we don't yet know is a pretty well established status for this problem. The class $\mathsf{NP}^{\mathsf{NP}}$ is also known as $\Sigma^{P}_2$, and is a class at the second level of the polynomial hierarchy. A simple reason why we can't just simulate an NP oracle with an NP machine is that we don't know how the NP machine could detect "no" instances. – Niel de Beaudrap Jul 12 '12 at 15:23
• Why is $NP^{NP}$ the same as $\Sigma_2^P$? – Lisa Jul 12 '12 at 15:27
• That is simply how $\Sigma_2^P$ is defined. Please read the Wikipedia page, or a textbook on computational complexity which covers the polynomial hierarchy. – Niel de Beaudrap Jul 12 '12 at 15:28

The class NPNP is also known as $\Sigma_2^P$, and is one of the classes at the second level of the polynomial hierarchy. The other classes at the second level are \begin{align*} \Delta_2^P &:= \mathsf{P}^{\mathsf{NP}}, \\ \Pi_2^P &:= \mathsf{coNP}^{\mathsf{NP}}. \end{align*} (All these classes would be the same if we used a coNP oracle; the only difference is in essence a logical negation of the output.) The classes of the third and higher levels of the hierarchy are defined by giving them yet further NP oracles: \begin{align*} \Delta_{k+1}^P &:= \mathsf{P}^{\,\Sigma_{k}^P} = \mathsf{P}^{\,\Pi_k^P}, \\[1ex] \Sigma_{k+1}^P &:= \mathsf{NP}^{\,\Sigma_{k}^P} = \mathsf{NP}^{\,\Pi_k^P}, \\[1ex] \Pi_{k+1}^P &:= \mathsf{coNP}^{\,\Sigma_{k}^P} = \mathsf{coNP}^{\,\Pi_k^P}. \\\end{align*} Again, the difference between the $\Sigma_k^P$ and $\Pi_k^P$ oracles is essentially negation of its output. We also define $\Delta_0^P = \Sigma_0^P = \Pi_0^P = \mathsf{P}$; using the definition above, you can see that this gives us $\Delta_1^P := \mathsf{P}$,  $\Sigma_1^P := \mathsf{NP}$, and $\Pi_1^P := \mathsf{coNP}$.
The various classes of the polynomial hierarchy are thought to be distinct; that is, no matter how many layers of NP oracles you provide, the computational power is not thought to stabilize at any point. If NPNP = NP, then the polynomial hierarchy collapses to it's first level: all of the $\Sigma_k^P$ classes for k ≥ 1 would be equal to NP (as would, for that matter, all of the $\Pi_k^P$ classes including coNP, as an NP machine could solve any problem in $\Pi_k^P$ by simulating some tower of NP oracles).
$\mathsf{NP}^{\mathsf{NP}}$ is known as the second level of polynomial hierarchy.
It is suspected that all levels of polynomial hierarchy are different. A machine with NP oracle can query it and negate the answer, therefore $\mathsf{NP}^{\mathsf{NP}} \supseteq \mathsf{coNP}$, while $\mathsf{NP} \supseteq \mathsf{coNP}$ seems unlikely.