# 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$.