principleMinor
Relation between $P$ vs $\mathit{NP}$ and $P^{\mathit{NP}}$ vs $\mathit{NP}^{\mathit{NP}}$ questions?
Viewed 0 times
questionsmathitbetweenandrelation
Problem
Given that both $P \subset \mathit{NP}\ ?$ and $P^{\mathit{NP}} \subset \mathit{NP}^{\mathit{NP}}\ ?$ are open questions.
Is it possible that
$P \subset \mathit{NP}$ and $P^{\mathit{NP}} =\mathit{NP}^{\mathit{NP}}$?
Or is it the case that $P \subset \mathit{NP}$ iff $P^{\mathit{NP}} \subset \mathit{NP}^{\mathit{NP}}$?
Is it possible that
$P \subset \mathit{NP}$ and $P^{\mathit{NP}} =\mathit{NP}^{\mathit{NP}}$?
Or is it the case that $P \subset \mathit{NP}$ iff $P^{\mathit{NP}} \subset \mathit{NP}^{\mathit{NP}}$?
Solution
We know that $\mathsf{P} \subseteq \mathsf{NP}$ and that $\mathsf{P}^{\mathsf{NP}} \subseteq \mathsf{NP}^{\mathsf{NP}}$; this follows directly from the definitions.
More interesting are the two reverse inclusions, $\mathsf{NP} \subseteq \mathsf{P}$ and $\mathsf{NP^{NP}} \subseteq \mathsf{P^{NP}}$. The former implies the latter: indeed, if $\mathsf{NP} \subseteq \mathsf{P}$ then $\mathsf{P} = \mathsf{NP} = \mathsf{P^{NP}} = \mathsf{NP^{NP}}$. The latter is not known to imply the former, and moreover, there are relativized worlds with respect to which the former is false but the latter is true. This means that there is an oracle $O$ (constructed by diagonalization) such that if all Turing machines have additional oracle access to $O$, then $\mathsf{P} \neq \mathsf{NP}$ but $\mathsf{P^{NP}} = \mathsf{NP^{NP}}$. Such an oracle was constructed by Heller, Relativized Polynomial Hierarchies Extending Two Levels.
More interesting are the two reverse inclusions, $\mathsf{NP} \subseteq \mathsf{P}$ and $\mathsf{NP^{NP}} \subseteq \mathsf{P^{NP}}$. The former implies the latter: indeed, if $\mathsf{NP} \subseteq \mathsf{P}$ then $\mathsf{P} = \mathsf{NP} = \mathsf{P^{NP}} = \mathsf{NP^{NP}}$. The latter is not known to imply the former, and moreover, there are relativized worlds with respect to which the former is false but the latter is true. This means that there is an oracle $O$ (constructed by diagonalization) such that if all Turing machines have additional oracle access to $O$, then $\mathsf{P} \neq \mathsf{NP}$ but $\mathsf{P^{NP}} = \mathsf{NP^{NP}}$. Such an oracle was constructed by Heller, Relativized Polynomial Hierarchies Extending Two Levels.
Context
StackExchange Computer Science Q#148038, answer score: 4
Revisions (0)
No revisions yet.