patternModerate
Does $NP^{NP}=NP$?
Viewed 0 times
doesstackoverflowprogramming
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#2712, answer score: 15
Revisions (0)
No revisions yet.