polynomial hierarchy

The polynomial hierarchy is a hierarchy of complexity classesPlanetmathPlanetmath generalizing the relationship between 𝒫 and 𝒩𝒫.

We let Σ0p=Π0p=Δ0p=𝒫, then Δi+1p=𝒫Σip and Σi+1p=𝒩𝒫Σip. Define Πip to be coΣip.

For instance Σ1p=𝒩𝒫𝒫=𝒩𝒫.

The complexity class 𝒫=iΣip.

The polynomial hierarchy is closely related to the arithmetical hierarchy; indeed, an alternate definition is almost identical to the definition of the arithmetical hierarchy but stricter rules on what quantifiersMathworldPlanetmath can be used.

When there is no risk of confusion with the arithmetical hierarchy, the superscript p can be dropped.

Title polynomial hierarchy
Canonical name PolynomialHierarchy
Date of creation 2013-03-22 13:02:11
Last modified on 2013-03-22 13:02:11
Owner Henry (455)
Last modified by Henry (455)
Numerical id 6
Author Henry (455)
Entry type Definition
Classification msc 68Q15
Defines PH