Complexity: Polynomial Hierarchy
Motivation§
The polynomial hierarchy is a generalisation upon the $\textbf{P}, \textbf{NP}$, and $\textbf{coNP}$ complexity classes.
A language $L \in \textbf{NP}$ iff there exists a polynomial-time Turing machine $\mathcal{M}$ such that
$$ x \in L \iff \exists w [\mathcal{M}(x, w) \text{ accepts}]. $$
A language $L \in \textbf{coNP}$ iff there exists a polynomial-time Turing machine $\mathcal{M}$ such that
$$ x \in L \iff \forall w [\mathcal{M}(x, w) \text{ accepts}]. $$
Then, it is a natural question to generalise upon these definitions, i.e. what does it mean to be given $x \in L$ such that
$$ \exists w_1 \forall w_2 [\mathcal{M}(x, w_1, w_2) \text{ accepts}]. $$
The Polynomial Hierarchy§
This page is primarily based off of “Computational Complexity: A Modern Approach”1 by S. Arora and B. Barak.
Polynomial Hierarchy
For every $i \geq 1$, a language $L \in \mathbf{\Sigma}_i$ iff there exists a polynomial-time Turing machine $\mathcal{M}$ and a polynomial $q$ such that
$$ x \in L \iff \exists w_1 \forall w_2 \dots Q_i w_i [\mathcal{M}(x, w_1, w_2, \dots, w_i) \text{ accepts}]. $$
where the domain for each $w_k$ is $\{0, 1\}^{q(|x|)}$, and $Q_i$ is $\exists$ if $i$ odd or $\forall$ otherwise.
Similarly, we say $L \in \mathbf{\Pi}_i$ iff there exists a Turing machine $\mathcal{M}$ and a polynomial $q$ such that
$$ x \in L \iff \forall w_1 \exists w_2 \dots Q_i w_i [\mathcal{M}(x, w_1, w_2, \dots, w_i) \text{ accepts}]. $$
where the domain for each $w_k$ is $\{0, 1\}^{q(|x|)}$, and $Q_i$ is $\forall$ if $i$ odd or $\exists$ otherwise.
Then, the polynomial hierarchy is defined as
$$ \textbf{PH} = \bigcup_{i=1}^{\infty} \mathbf{\Sigma}_i. $$
Notice that $\mathbf{\Sigma}_1 = \textbf{NP}$ and $\mathbf{\Pi}_1 = \textbf{coNP}$, and that $\mathbf{\Pi}_k = \textbf{co}\mathbf{\Sigma}_k$.
$$\mathbf{\Sigma}_k \subseteq \mathbf{\Sigma}_{k+1}, \mathbf{\Sigma}_k \subseteq \mathbf{\Pi}_{k+1}, \mathbf{\Pi}_k \subseteq \mathbf{\Pi}_{k+1}, \mathbf{\Pi}_k \subseteq \mathbf{\Sigma}_{k+1}.$$
Utilizing these properties, we get that
$$ \mathbf{\Sigma}_k = \begin{cases} \textbf{P} & \text{ if } k = 0,\\ \textbf{NP}^{\mathbf{\Sigma}_{k-1}} & \text{ if } k > 0. \end{cases} $$
MAX-INDSET§
Recall that the INDSET problem, a set of vertices that do not share an edge on a graph.
$$ \textbf{INDSET} \vcentcolon= \{(G, k) : G \text{ has an independent set of size } \geq k\} $$
This is a $\textbf{NP}$ problem, because if we are given a solution to this problem we can verify in polynomial-time that it is correct; and it is also a strongly NP complete problem.
Then, we can ask if given an independent set if it is the maximal independent set, i.e.
$$ \textbf{MAX-INDSET} \vcentcolon= \{(G, k) : \text{the largest independent set in } G \text{ has size equal to } k\} $$
If we are given a candidate solution, we can efficiently verify that it is indeed an independent set. However, we cannot efficiently certify that it is the maximal independent set. Therefore, $\textbf{MAX-INDSET} \notin \textbf{NP}$. There is also no easy way to show that $(G, k) \notin \textbf{MAX-INDSET}$ if $G$ has a maximal independent set that is smaller than $k$, so $\textbf{MAX-INDSET} \notin \textbf{coNP}$.
We get that $\textbf{MAX-INDSET} \in \mathbf{\Sigma_2}$, because $(G, k) \in \textbf{MAX-INDSET}$ iff there exists an independent set containing $k$ vertices, such that for all sets containing strictly more than $k$ vertices are not independent sets.
The Polynomial Hierarchy Collapse§
Theorem: Polynomial Hierarchy Collapse
If there exists $i$ such that $\mathbf{\Sigma}_i = \mathbf{\Pi}_i$, then $\textbf{PH} = \mathbf{\Sigma}_i$.
Corollary
If $\textbf{P} = \textbf{NP}$, then $\textbf{PH} = \mathbf{\Sigma}_0 = \textbf{P}$.
We will show by induction the collapse of the hierarchy under the assumption that $\textbf{P} = \textbf{NP} = \textbf{coNP}$.
For the base case $i = 1$, we get that $\mathbf{\Sigma}_1, \mathbf{\Pi}_1 \subseteq \textbf{P}$ under our assumption $\textbf{P} = \textbf{NP} = \textbf{coNP}$.
Assume the relation holds for $i - 1$. For $i$, let $L \in \mathbf{\Sigma}_i$. Then, by definition there exists a polynomial-time Turing machine $\mathcal{M}$ and a polynomial $q$ satisfying
$$ x \in L \iff \exists w_1 \forall w_2 \dots Q_iw_i [\mathcal{M}(x, w_1, w_2, \dots, w_i)\text{ accepts}], $$
where the domain of each quantifier is $\{0, 1\}^{q(|x|)}$, and $Q_i$ is the appropriate quantifier in the expression. Then, we define $L’$ to satisfy
$$ w_1 \in L’ \iff \exists\forall w_2 \dots Q_iw_i [\mathcal{M}(w_1, w_2, \dots, w_i)\text{ accepts}]. $$
So, $L’ \in \mathbf{\Pi}_{i-1}$ and as we assumed $i - 1$ holds $L’ \in \textbf{P}$. This implies that there exists a polynomial-time Turing machine $\mathcal{M}’$ satisfying
$$ x \in L \iff \exists w_1[\mathcal{M}’ (x, w_1)\text{ accepts}]. $$
As there exists an efficient certifier $\mathcal{M}’$, we get that $L \in \textbf{NP}$ which implies $L \in \textbf{P}$ with our assumption.
Using the same technique, we can then show that if $L \in \mathbf{\Pi}_i$, then $L \in \textbf{coNP}$ which again implies $L \in \textbf{P}$ by our assumption.
Therefore, if $\textbf{P} = \textbf{NP}$, then $\textbf{PH} = \textbf{P}$.
Complete Problems in the Polynomial Hierarchy§
Complete Problem
A language $L$ is considered to be $\mathbf{\Sigma}_i$-complete iff $L \in \mathbf{\Sigma}_i$ and $\forall L’ \in \mathbf{\Sigma}_i, L’ \leq_p L$.
We also define $\mathbf{\Pi}_i$-complete and $\textbf{PH}$-complete problems in the same manner.
Then, for every $i$ there exists $\mathbf{\Sigma}_i$-complete and $\mathbf{\Pi}_i$-complete problems, however, it is unlikely for a problem to be $\textbf{PH}$-complete.
Claim
Sps. $L$ that is $\textbf{PH}$-complete, then there must exist an $i$ such that $\textbf{PH} = \mathbf{\Sigma}_i$.
Given that $\textbf{PH} = \cup_{k=0}^{i}\mathbf{\Sigma}_k$, then if $L \in \textbf{PH}$ and is $\textbf{PH}$-complete, every other language $L’ \in \textbf{PH}$ can be reduced in polynomial-time into a problem in $\mathbf{\Sigma}_i$ and then into $L$. Therefore $\textbf{PH} \subseteq \mathbf{\Sigma}_i$.
For example, factorization is a problem in $\textbf{NP}\cap\textbf{coNP}$. If we were able to prove that it is either $\textbf{NP}$- or $\textbf{coNP}$-complete, then $\textbf{NP} = \textbf{coNP}$ which would mean $\textbf{PH} \subseteq \mathbf{\Sigma}_1$.