polynomial hierarchy is a hierarchy

The polynomial hierarchy is a hierarchy. Specifically:



To see that ΣipΠipΔi+1p=𝒫Σip, observe that the machine which checks its input against its oracle and accepts or rejects when the oracle accepts or rejects (respectively) is easily in 𝒫, as is the machine which rejects or accepts when the oracle accepts or rejects (respectively). These easily emulate Σip and Πip respectively.

Since 𝒫𝒩𝒫, it is clear that ΔipΣip. Since 𝒫𝒞 is closed under complementation for any complexity classPlanetmathPlanetmath 𝒞 (the associated machines are deterministicMathworldPlanetmath and always halt, so the complementary machine just reverses which states are accepting), if L𝒫ΣipΣip then so is L¯, and therefore LΠip.

Unlike the arithmetical hierarchy, the polynomial hierarchy is not known to be proper. Indeed, if 𝒫=𝒩𝒫 then 𝒫=𝒫, so a proof that the hierarchy is proper would be quite significant.

Title polynomial hierarchy is a hierarchy
Canonical name PolynomialHierarchyIsAHierarchy
Date of creation 2013-03-22 13:02:14
Last modified on 2013-03-22 13:02:14
Owner uzeromay (4983)
Last modified by uzeromay (4983)
Numerical id 5
Author uzeromay (4983)
Entry type Result
Classification msc 68Q15