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

  • $\begingroup$ Not necessarily. I think this is an open question, rearding the polynomial hirarchy - whether it collapses to a finite level or not. $\endgroup$
    – nir shahar
    Dec 30 '21 at 13:32
  • $\begingroup$ 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? $\endgroup$
    – J.Doe
    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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.