In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP.[1] Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.
Classes within the hierarchy have complete problems (with respect to polynomial-time reductions) that ask if quantified Boolean formulae hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level.
There are multiple equivalent definitions of the classes of the polynomial hierarchy.
For the oracle definition of the polynomial hierarchy, define
P | |
\Delta | |
0 |
:=
P | |
\Sigma | |
0 |
:=
P | |
\Pi | |
0 |
:=P,
where P is the set of decision problems solvable in polynomial time. Then for i ≥ 0 define
P | |
\Delta | |
i+1 |
:=
| |||||||
P |
P | |
\Sigma | |
i+1 |
:=
| |||||||
NP |
P | |
\Pi | |
i+1 |
:=
| |||||||
coNP |
where
P\rm
NP\rm
coNP\rm
P | |
\Sigma | |
1 |
=NP,
P | |
\Pi | |
1 |
=coNP
P | |
\Delta | |
2 |
=
PNP |
For the existential/universal definition of the polynomial hierarchy, let be a language (i.e. a decision problem, a subset of *), let be a polynomial, and define
\existspL:=\left\{x\in\{0,1\}* \left| \left(\existsw\in\{0,1\}\leq\right)\langlex,w\rangle\inL\right.\right\},
where
\langlex,w\rangle\in\{0,1\}*
\existspL
|w|\leqp(|x|)
\existspL
x\in\existspL
\langlex,w\rangle\inL
\forallpL:=\left\{x\in\{0,1\}* \left| \left(\forallw\in\{0,1\}\leq\right)\langlex,w\rangle\inL\right.\right\}
\left(\existspL\right)\rm=\forallpL\rm
\left(\forallpL\right)\rm=\existspL\rm
Let be a class of languages. Extend these operators to work on whole classes of languages by the definition
\existsPl{C}:=\left\{\existspL | pisapolynomialandL\inl{C}\right\}
\forallPl{C}:=\left\{\forallpL | pisapolynomialandL\inl{C}\right\}
Again, De Morgan's laws hold:
co\existsPl{C}=\forallPcol{C}
co\forallPl{C}=\existsPcol{C}
col{C}=\left\{Lc|L\inl{C}\right\}
The classes NP and co-NP can be defined as
NP=\existsPP
coNP=\forallPP
P | |
\Sigma | |
0 |
:=
P | |
\Pi | |
0 |
:=P
P | |
\Sigma | |
k+1 |
:=\existsP
P | |
\Pi | |
k |
P | |
\Pi | |
k+1 |
:=\forallP
P | |
\Sigma | |
k |
Note that
NP=
P | |
\Sigma | |
1 |
coNP=
P | |
\Pi | |
1 |
This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers.
An alternating Turing machine is a non-deterministic Turing machine with non-final states partitioned into existential and universal states. It is eventually accepting from its current configuration if: it is in an existential state and can transition into some eventually accepting configuration; or, it is in a universal state and every transition is into some eventually accepting configuration; or, it is in an accepting state.[3]
We define
P | |
\Sigma | |
k |
P | |
\Pi | |
k |
If we omit the requirement of at most k – 1 swaps between the existential and universal states, so that we only require that our alternating Turing machine runs in polynomial time, then we have the definition of the class AP, which is equal to PSPACE.[5]
The union of all classes in the polynomial hierarchy is the complexity class PH.
The definitions imply the relations:
P | |
\Sigma | |
i |
\subseteq
P | |
\Delta | |
i+1 |
\subseteq
P | |
\Sigma | |
i+1 |
P | |
\Pi | |
i |
\subseteq
P | |
\Delta | |
i+1 |
\subseteq
P | |
\Pi | |
i+1 |
P | |
\Sigma | |
i |
=
P | |
co\Pi | |
i |
Unlike the arithmetic and analytic hierarchies, whose inclusions are known to be proper, it is an open question whether any of these inclusions are proper, though it is widely believed that they all are. If any
P | |
\Sigma | |
k |
=
P | |
\Sigma | |
k+1 |
P | |
\Sigma | |
k |
=
P | |
\Pi | |
k |
i>k
P | |
\Sigma | |
i |
=
P | |
\Sigma | |
k |
P | |
\Pi | |
1 |
The question of collapse to the first level is generally thought to be extremely difficult. Most researchers do not believe in a collapse, even to the second level.
The polynomial hierarchy is an analogue (at much lower complexity) of the exponential hierarchy and arithmetical hierarchy.
It is known that PH is contained within PSPACE, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only if second-order logic over finite structures gains no additional power from the addition of a transitive closure operator over relations of relations (i.e., over the second-order variables).[8]
If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a
P | |
\Sigma | |
k |
Each class in the polynomial hierarchy contains
P | |
\leq | |
\rmm |
P | |
\leq | |
\rmm |
L\inl{C}
A
P | |
\leq | |
\rmm |
L
A\inl{C}
Ki
P | |
\Sigma | |
i |
P | |
\Sigma | |
i+1 |
=
Ki | |
NP |
P | |
\Pi | |
i+1 |
=
Ki | |
coNP |
P | |
\Sigma | |
2 |
=NPSAT
The Sipser–Lautemann theorem states that the class BPP is contained in the second level of the polynomial hierarchy.
Kannan's theorem states that for any k,
\Sigma2
Toda's theorem states that the polynomial hierarchy is contained in P#P.