From this link Does $NP^{NP}=NP$?
I learned that if $NP^{NP} = NP$, then the polynomial hierarchy collapses to it's first level.
But how to prove it？
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Prove that $\Sigma_i^P = NP$ for $i \ge 2$ by induction on $i$. The base case is $i=2$ and is trivial since, by hypothesis, $\Sigma_2^P = NP^{NP} = NP$. For the inductive step, suppose that $\Sigma_i^P = NP$ and notice that $\Sigma_{i+1}^P = NP^{\Sigma_i^P} = NP^{NP}= NP$.
Now, for $i \ge 2$, you can observe that $NP \subseteq \Delta_{i}^P \subseteq \Pi_i^P \subseteq \Delta_{i+1}^P \subseteq \Sigma_{i+1}^P = NP$.
