Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

Define

$\Delta _{0}{\mbox{P}}=\Sigma _{0}{\mbox{P}}=\Pi _{0}{\mbox{P}}={\mbox{P}}$

Then for i ≥ 0 define

$\Delta _{i+1}{\mbox{P}}={\mbox{P}}^{\Sigma _{i}{\rm {P}}}$

$\Sigma _{i+1}{\mbox{P}}={\mbox{NP}}^{\Sigma _{i}{\rm {P}}}$

$\Pi _{i+1}{\mbox{P}}={\mbox{co-NP}}^{\Sigma _{i}{\rm {P}}}$

Where A^B is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some problem in class B. For example, the class Δ₁P = P^NP is the class of problems solvable in polynomial time with an oracle for some problem in NP.

This gives us the relations:

$\Sigma _{i}{\mbox{P}}\subseteq \Delta _{i+1}{\mbox{P}}$

$\Pi _{i}{\mbox{P}}\subseteq \Delta _{i+1}{\mbox{P}}$

An equivalent definition in terms of alternating Turing machines defines Σ_iP (Π_iP) as the set of decision problems solvable in polynomial time on an i-alternating Turing machine starting in an existential (universal) state.

The union of all classes in the polynomial hierarchy is the complexity class PH.