9
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Jul 12 '12 at 19:21

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

  • 16
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Jul 12 '12 at 15:23
  • $\begingroup$ Why is $NP^{NP}$ the same as $\Sigma_2^P$? $\endgroup$ – Lisa Jul 12 '12 at 15:27
  • 5
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Jul 12 '12 at 15:28
12
$\begingroup$

To reformulate my comments as an answer, and to expand a bit:

We don't know whether NPNP = NP — it's a notoriously open problem in complexity theory, though as with P versus NP we suspect that they are not equal. One of the reasons why we don't know how to simulate an NP oracle with an NP machine is that we don't know how the NP machine could detect "no" instances of problems submitted to the oracle.

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy