Skip to main content
2 of 2
improved formatting with LaTeX, definition of the acronym PH

Surely this class, being $\text{NP}^\text{NP}$, is by definition equal to $\Sigma_2^p$. In particular, if the Polynomial Hierarchy (PH) does not collapse, then it does not contain $\Pi_2^p$.

Martin Orr
  • 1.5k
  • 10
  • 24