# Relation between $P$ vs $\mathit{NP}$ and $P^{\mathit{NP}}$ vs $\mathit{NP}^{\mathit{NP}}$ questions?

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

• Not necessarily. I think this is an open question, rearding the polynomial hirarchy - whether it collapses to a finite level or not. Dec 30 '21 at 13:32
• true. Its true that polynomial hierarchy collapse is an open Q. But, question is more regarding the power of two classes with and without oracle (of course that assumes and conditional on the polynomial hierarchy collapse, which even though unlikely is not impossible). Hopefully someone can answer? Dec 30 '21 at 16:04

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.