9. Polynomial Hierarchy

We saw in the last lecture that the \(\mathsf{Clique}\) language, where the input is \(\left< G \right> \left< k \right>\) and the task is to determine if the graph \(G\) has a clique of size \(k\), is in \(\mathbf{NP}\). We can also consider the similar languages

and

Neither of these problems appear to be in \(\mathbf{NP}\), at least at first glance. After all, what kind of certificate could help you efficiently verify that there is no large clique in a graph? Or that a particular clique is the largest clique in a graph? These two languages, however, both belong to a larger class called the polynomial hierarchy.

The Class coNP

The class \(\mathbf{NP}\) can be viewed as the class of languages for which there exists a certificate that convinces the verifier to accept. We can view this type of verifier as a cautious verifier, in that it only accepts when it is provided truly compelling evidence that it should do so; its default behaviour is to reject otherwise.

We can define the complement class to \(\mathbf{NP}\), called \(\mathbf{coNP}\) that captures the opposite type of verifier: an audacious verifier that always accepts unless the certificate provides truly compelling evidence that it should not do so. To distinguish this type of verifier from the cautious ones introduced for \(\mathbf{NP}\), let us call these \(\forall\)-verifiers.

Definition. The language \(L(V)\) decided by the \(\forall\)-verifier \(V\) that halts on all input pairs is

\[L(V) = \{ x \in \{0,1\}^* : \forall c \in \{0,1\}^*, V \mbox{ accepts } (x,c) \}.\]

A polynomial-time \(\forall\)-verifier is a \(\forall\)-verifier that decides its language and has time cost \(O(n^k)\) for some constant \(k \ge 0\).

The class \(\mathbf{coNP}\) is the set of all languages that can be decided by polynomial-time \(\forall\)-verifiers.

The name of the class \(\mathbf{coNP}\) is justified by the observation that a language is in this class if and only if its complement is in \(\mathbf{NP}\).

Proposition 1. The language \(L \subseteq \{0,1\}^*\) is in \(\mathbf{NP}\) if and only if its complement \(\overline{L}\) is in \(\mathbf{coNP}\).

Proof. For any verifier \(V\), let \(V'\) be the \(\forall\)-verifier obtained by interchanging the Accept and Reject actions of \(V\). Then a string \(x \in \{0,1\}^*\) is accepted by \(V\) if and only if the same string is rejected by \(V'\), because a certificate \(c\) that causes \(V\) to accept \((x,c)\) also causes \(V'\) to reject the same input pair. So \(L\) has a polynomial-time verifier \(V\) if and only if there is a polynomial-time \(\forall\)-verifier \(V'\) that rejects exactly the set \(L\) of strings or, in other words, if \(V'\) decides \(L\).

Does \(\mathbf{NP} = \mathbf{coNP}\)? No one knows. Though this might not be too surprising: if you manage to prove that \(\mathbf{NP} \neq \mathbf{coNP}\), this will imply that \(\mathbf{P} \neq \mathbf{NP}\) as well. (Why?) But, interestingly, if you do manage to show that \(\mathbf{P} \neq \mathbf{NP}\), it will not settle the \(\mathbf{NP}\) vs. \(\mathbf{coNP}\) question.

The Class PH

Once we have defined regular verifiers (which we may call \(\exists\)-verifiers for the rest of this lecture to prevent any confusion) and \(\forall\)-verifiers, it’s natural to extend the notion of verifiers even further. For instance, motivated by the \(\mathsf{MaxClique}\) language, we may define \(\exists\forall\)-verifiers.

Definition. The language \(L(V)\) decided by the \(\exists\forall\)-verifier \(V\) that halts on all input tuples \((x,c_1,c_2)\) is

\[L(V) = \{ x \in \{0,1\}^* : \exists c_1 \forall c_2 \mbox{ such that } V \mbox{ accepts } (x,c_1,c_2) \}.\]

The class of all languages that can be decided by polynomial-time \(\exists \forall\)-verifiers is denoted by \(\mathbf{\Sigma_2}\).

And if we interchange the position of the \(\exists\) and \(\forall\) quantifiers in the definition above, we obtain the notion of \(\forall \exists\)-verifiers. The class of all languages that can be decided by polynomial-time \(\forall \exists\)-verifiers is denoted by \(\mathbf{\Pi_2}\).

The language \(\mathsf{MaxClique}\) is in \(\mathbf{\Sigma_2}\). One way to define a polynomial-time \(\exists \forall\)-verifier for this language is to accept \((\left<G\right>\left< k \right>, c_1,c_2)\) if and only if \(c_1\) indicates the position of \(k\) vertices that form a clique in \(G\) and \(c_2\) indicates a set of vertices in the graph that does not represent a clique of size greater than \(k\). And the same verifier with \(c_1\) and \(c_2\) interchanged shows that \(\mathsf{MaxClique}\) is in \(\mathbf{\Pi_2}\) as well. So \(\mathsf{MaxClique} \in \mathbf{\Sigma_2} \cap \mathbf{\Pi_2}\).

By adding more quantifiers in the same way, we can define the classes \(\mathbf{\Sigma_3}\), \(\mathbf{\Pi_3}\), \(\mathbf{\Sigma_4}\), \(\mathbf{\Pi_4}\), etc. And for consistency, we can also write \(\mathbf{\Sigma_1} = \mathbf{NP}\) and \(\mathbf{\Pi_1} = \mathbf{coNP}\). (We can even write \(\mathbf{\Sigma_0} = \mathbf{\Pi_0} = \mathbf{P}\), if we really want to tie all the polynomial-time complexity classes together.) The union of all those classes forms the polynomial hierarchy.

Definition. The polynomial hierarchy is the class of languages defined by

\[\mathbf{PH} = \bigcup_{k \ge 1} \mathbf{\Sigma_k} = \bigcup_{k \ge 1} \mathbf{\Pi_k}.\]

Note that for every \(k \ge 1\), the classes \(\mathbf{\Sigma_k}\) and \(\mathbf{\Pi_k}\) are both contained in \(\mathbf{\Sigma_{k+1}} \cap \mathbf{\Pi_{k+1}}\) since the latter two classes can always ignore one of their \(k+1\) certificate strings. This observation justifies the implicit claim that the two definitions for \(\mathbf{PH}\) give the same class of languages.

Properties of PH

The polynomial hierarchy has a number of interesting properties. The first is that languages in \(\mathbf{PH}\) cannot have arbitrary time complexity.

Proposition 2. \(\mathbf{PH} \subseteq \mathbf{EXP}\).

Proof. Let us prove by induction on \(k\) that \(\mathbf{\Sigma_k}\) and \(\mathbf{\Pi_k}\) are contained in \(\mathbf{EXP}\).

In the base case where \(k=1\), consider any \(L \in \mathbf{\Sigma_1} = \mathbf{NP}\). Without loss of generality, we can assume that a polynomial-time verifier \(V\) for \(L\) only accepts certificates of length polynomial in \(n\). Then we can design a (standard) exponential-time Turing machine \(M\) that simulates \(V\) on input \(x\) by iterating over all possible certificates \(c\) of polynomial length and accepting if and only if \(V\) accepts the pair \((x,c)\).

The proof that \(\mathbf{Pi_1} = \mathbf{coNP}\) is contained in \(\mathbf{EXP}\) proceeds in the same way, with the only modification that \(M\) accepts \(x\) if and only if \(V\) accepts \((x,c)\) for every polynomial-length certificate \(c\).

For the induction step, consider any \(L \in \mathbf{\Sigma_k}\) for some \(k \ge 2\). Let \(V\) be a \(\mathbf{\Sigma_k}\)-verifier for \(L\). The string \(x\) is in \(L\) if and only if \(\exists c_1 \forall c_2 \exists \cdots \exists/\forall c_k\) for which \(V\) accepts \((x,c_1,c_2,\ldots,c_k)\). Once again, we can assume that \(c_1,\ldots,c_k\) are all of polynomial length. By the induction hypothesis on \(\mathbf{\Pi_{k-1}}\), we know that there exists an exponential-time Turing machine \(M\) that accepts the input \((x,c_1)\) for any string \(c_1\) if and only if \(\forall c_2 \cdots \exists/\forall c_k\) such that \(V\) accepts \((x,c_1,c_2,\ldots,c_k)\). So we obtain an exponential-time Turing machine for \(L\) by completing an exhaustive search over all polynomial-length certificates \(c_1\) and accepting if and only if there is one such certificate for which \(M\) accepts \((x,c_1)\).

Once again, the proof that \(\mathbf{\Pi_k}\) is essentially identical, except that we accept only if every polynomial-length certificate \(c_1\) causes \(M\) to accept \((x,c_1)\).

This completes the proof that \(\mathbf{\Sigma_k}, \mathbf{\Pi_k} \subseteq \mathbf{EXP}\) for each \(k \ge 1\) and therefore that \(\mathbf{PH} \subseteq \mathbf{EXP}\) as well.

We say that the polynomial hierarchy collapses to the \(k\)th level if we can show that \(\mathbf{PH} = \mathbf{\Sigma_k}\). We do not expect that the polynomial hierarchy collapses to any level. Or, in other words, we expect that \(\mathbf{\Sigma_k} \subsetneq \mathbf{\Sigma_{k+1}}\) for every \(k \ge 1\). Of course, as always you should take any of these “we expect” statements with an appropriate amount of skepticism. It could be that no one can prove that statement because it’s false!

One way we could prove that the polynomial hierarchy does collapse is by extending the notion of \(\mathbf{NP}\)-completeness to the other classes of the polynomial hierarchy. In fact, the notion of completeness is meaningful for any class of languages that includes \(\mathbf{P}\).

Definition. For any class \(\mathcal{C}\) of languages that includes \(\mathbf{P}\), a language \(L \subseteq \{0,1\}^*\) is \(\mathcal{C}\)-complete if \(L \in \mathcal{C}\) and every \(A \in \mathcal{C}\) satisfies \(A \le_{\mathbf{P}} L\).

The classes \(\mathbf{\Sigma_k}\) and \(\mathbf{\Pi_k}\) for each \(k \ge 1\) all have complete languages. But the class \(\mathbf{PH}\) does not unless the polynomial hierarchy collapses.

Theorem 3. If the polynomial hierarchy does not collapse (i.e., if \(\mathbf{\Sigma_k} \subsetneq \mathbf{\Sigma_{k+1}}\) for all \(k \ge 1\)) then there is no \(\mathbf{PH}\)-complete language.

Proof. Assume on the contrary that the language \(L\) is \(\mathbf{PH}\)-complete.

Since \(L \in \mathbf{PH}\), it must be included in the class \(\mathbf{\Sigma_k}\) for some \(k \ge 1\). Fix any language \(A \in \mathbf{PH}\). Since \(L\) is \(\mathbf{PH}\)-complete, \(A \le_P L\). But this means that \(A \in \mathbf{\Sigma_k}\) because for any string \(x \in \{0,1\}^*\), we can convert it to \(f(x)\) in polynomial time such that \(x \in A\) if and only if \(f(x) \in L\). And we can then use the verifier for \(L\) to decide \(A\).

This means that \(\mathbf{PH} \subseteq \mathbf{\Sigma_k}\), contradicting the hypothesis that the polynomial hierarchy does not collapse.