The Polynomial Hierarchy

Definition#

There are many equivalent characterizations of the polynomial hierarchy. Of which the first one is the most similar to hierarchies in mathematical logic (arithmetic hierarchy, Borel hierarchy, etc.), namely in terms of the set of languages defined via polynomial-time predicates together with alternating \(\forall\) and \(\exists\).

Definition. For \(i\geq 1\), a language \(L\) is in \(\mathbf{\Sigma}^p_i\) if there is a polynomial-time Turing machine \(M\) and a polynomial \(q\) such that
 

\[x\in L \Leftrightarrow \exists u_1 \in \{0,1\}^{q(|x|)}\forall u_2\in \{0,1\}^{q(|x|)}\ldots Q_i u_i \in \{0,1\}^{q(|x|)} M(x,u_1,\ldots, u_i) = 1,\]

where \(Q_i\) denotes \(\forall\) or \(\exists\) depending on whether \(i\) is even or odd, respectively.
The polynomial hierarchy is the set \(\mathsf{PH} = \bigcup_i \mathbf{\Sigma}_i^p\).

Note that \(\mathbf{\Sigma}^p_1 = \mathbf{NP}\). For every \(i\), we may define \(\mathbf{\Pi}^p_i = \text{co}\mathbf{\Sigma}^p_i = \{\overline{L}: L \in \mathbf{\Sigma}^p_i\}\). Thus \(\mathbf{\Pi}^p_1 = \text{co}\mathbf{NP}\).

Since \(\mathbf{\Sigma}^p_i \subseteq \mathbf{\Pi}^p_{i+1} \subseteq \mathbf{\Sigma}^p_{i+2}\), we have \(\mathsf{PH} = \bigcup_{i>0} \mathbf{\Pi}^p_i\).