Polynomial hierarchy

TheoremIf P = NP then the polynomial hierarchy collapses to P#●ready to prove

If the complexity classes P and NP are equal, then the polynomial hierarchy PH, the union of the classes \(\Sigma_k^p\) over all natural numbers \(k\), is equal to P.

public theorem_wanted ph_collapses :
    MetaMathlibExt.ComplexityTheory.P = MetaMathlibExt.ComplexityTheory.NP →
      PH = MetaMathlibExt.ComplexityTheory.P

Sources

• S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009 (PH collapses to P if P = NP); L. J. Stockmeyer, "The polynomial-time hierarchy", Theoretical Computer Science 3 (1977), 1-22.

Uses 4

Statement usesThe polynomial hierarchy · Complexity classes · The complexity class NP · The complexity class P

TheoremThe polynomial hierarchy is contained in PSPACE#●ready to prove

Every decision problem in the polynomial hierarchy PH belongs to PSPACE.

public theorem_wanted ph_subset_pspace :
    PH ⊆ PSPACE

Sources

• L. J. Stockmeyer, "The polynomial-time hierarchy", Theoretical Computer Science 3 (1977), 1-22; S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009, Theorem 5.4.

Uses 4

Statement usesThe polynomial hierarchy · Polynomial space for decision problems · Complexity classes · Decision problems

2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.