I cannot see whether the implication in my question title holds. To me, it sounds reasonable to assume that, but I cannot find any source stating that this is true, false, or unknown at the moment.

So, does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?


No, this implication is not known to be true, however it is believed that those are all separate classes. (Unfortunately, I don't have any references to back up my claim now, but I still post this as an answer to point out the following.)

You are asking whether $\text{P} \neq \text{NP}$ implies that the polynomial hierarchy $(\text{PH})$ does not collapse to its first level.

The class $\text{NP}^\text{NP}$ is also known as $\Sigma_2^P$ which is one of the classes on the second level of the polynomial hierarchy.


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.