patternMinor
Does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?
Viewed 0 times
neqmathcalimplydoes
Problem
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}}$?
So, does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?
Solution
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.
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.
Context
StackExchange Computer Science Q#127110, answer score: 4
Revisions (0)
No revisions yet.