Skip to main content
MathOverflow

Return to Answer

improved formatting with LaTeX, definition of the acronym PH
Source Link
edit approved Sep 23, 2022 at 8:43
Tomáš Peitl
edit approved Sep 23, 2022 at 8:43
Tomáš Peitl
  • 83
  • 1
  • 7

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

Surely this class, being NP^NP, is by definition equal to Sigma2. In particular, if PH does not collapse, then it does not contain Pi2.

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$.

Source Link
Martin Orr
Martin Orr
  • 1.5k
  • 10
  • 24

Surely this class, being NP^NP, is by definition equal to Sigma2. In particular, if PH does not collapse, then it does not contain Pi2.