7. 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. Fix any language \(L \in \mathbf{PH}\). Then \(L \in \mathbf{\Sigma_k}\) for some finite \(k \ge 1\). Let \(V\) be a \(\Sigma_k\)-verifier for \(L\).

We can decide \(L\) with a deterministic Turing machine \(M\) that does an exhaustive search over all polynomial-length certificate strings \(c_1,c_2,\ldots,c_k\). For each set of \(k\)-certificate strings, we simulate \(V\) to see if it accepts \((x,c_1,\ldots,c_k)\). If it does, we halt and accept. Otherwise we move on to the next \(k\)-tuple of certificates. If \(V\) rejects all possible \(k\)-tuples of certificates, then we reject.

It should be clear that the machine \(M\) decides \(L\). It remains to bound its time complexity. If the maximum lengths of the \(k\) certificates that are considered by \(V\) are the polynomials \(p_1,\ldots,p_k\), then the total number of \(k\)-tuples of certificates considered by the simulation on input \(x \in \{0,1\}^n\) is \(2^{p_1(n)} \cdot 2^{p_2(n)} \cdots 2^{p_k(n)} = 2^{p_1(n) + p_2(n) + \cdots + p_k(n)}.\) But the sum of polynomials is also a polynomial, so the number of candidates to examine is \(2^{O(n^\ell)}\) for some constant \(\ell\). And \(V\)’s simulation for each of these candidates has time cost polynomial in \(n\), so the overall time cost of \(M\) is less than \(2^{O(n^{\ell+1})}\).

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.

Eric Blais ©2024 — Last edited on Jan. 29, 2024