6. P vs. NP

One of the big open problems in computer science today is the \(\mathbf{P}\) vs. \(\mathbf{NP}\) question. We are now in a position to examine it more precisely.

The Class NP

Many natural languages lie in the class \(\mathbf{P}\). And the Time Hierarchy Theorem shows that \(\mathbf{P} \neq \mathbf{EXP}\) so we know that there exist some decidable problems that are not in \(\mathbf{P}\). But how big is \(\mathbf{P}\), exactly?

A good way to try to determine the boundary of the class \(\mathbf{P}\) is to identify languages that are “almost” in \(\mathbf{P}\) but for which we can’t determine if they are solvable in polynomial time or not. One good such candidate is the language

(Recall that a clique is a subset \(C \subseteq V\) of vertices of \(G = (V,E)\) such that the induced subgraph on this set of vertices forms a complete graph.)

One interesting property of the \(\textsf{CLIQUE}\) language is that it is easy to verify that a graph has a clique of size \(k\) when someone else points out the vertices contained in the set \(C\). To see this, note that checking whether a given pair of vertices \(v,w \in V\) are connected by an edge in \(G\) can easily be done in polynomial-time by inspecting the description of \(G\). And given a set \(C \subseteq V\) of \(k\) vertices, checking that it forms a complete subgraph requires checking the presence of only \(O(k^2)\) edges in the graph. So, overall, verifying whether \(C\) is indeed a large clique can be done in polynomial time.

Many other natural problems have the property that they are verifiable in polynomial-time. And we can make this notion precise by extending our usual notion of Turing machines.

Definition. A verifier is a Turing machine that in addition to its usual tape also has a special certificate tape. The input to a verifier is a pair \((x,c)\) with the input string \(x\) written on the first (normal) tape and the certificate string \(c\) written on the certificate tape.

The execution of a verifier follows the same rules as standard Turing machines. The only notable distinctions are that the certificate is read-only and that the tape heads on the standard input tape and on the certificate tape can move independently of each other. However, the most significant difference between standard Turing machines and verifiers is in the definition of the language that is decided or recognized by a verifier.

Definition. The language \(L(V)\) recognized by the verifier \(V\) is

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

The verifier \(V\) decides \(L(V)\) if it halts on all input pairs \((x,c)\).

A polynomial-time verifier is a verifier that decides its language and has time cost \(O(n^k)\) for some constant \(k \ge 0\). One important detail: the time cost of a verifier is measured in terms of the length of the input string only. In particular, this means that for any polynomial-time verifier and every \(x \in L(V)\), there must be a certificate of length polynomial in \(|x|\) that causes \(V\) to accept. (Moreover, to satisfy the time cost condition, there must also be some polynomial \(q\) for which \(V\) rejects all pairs \((x,c)\) when \(|c| > q(|x|)\) without even reading the entire certificate string.)

The class \(\mathbf{NP}\) is the set of all languages that can be decided by polynomial-time verifiers. (Incidentally, the name \(\mathbf{NP}\) stands for \(\mathbf{N}\)ondeterministic \(\mathbf{P}\)olynomial-time, since we can define the same class with nondeterministic Turing machines instead of verifiers.)

The \(\mathbf{P}\) vs. \(\mathbf{NP}\) problem is then asking the following question:

  Can every language that is efficiently verifiable also be efficiently computable?

It may seem obvious that the answer should be no… after all, having someone point out a valid solution to a problem and just having to verify its correctness seems like it should be quite a bit easier than figuring out the solution to the problem on your own for some hard problems. Yet, trying to confirm (or contradict!) this intuition has proven to be surprisingly elusive. And not only that, but studying this question has also led to numerous fascinating insights into the power of computers, as we will continue to explore throughout the rest of the course.

NP-Completeness

One of the most powerful tools in the study of the \(\mathbf{P}\) vs. \(\mathbf{NP}\) problem is the notion of polynomial-time reductions.

Definition. The language \(A \subseteq \{0,1\}^*\) is polynomial-time reducible to the language \(B \subseteq \{0,1\}^*\), denoted

\[A \le_{\mathbf{P}} B\]

if and only if there exists a function \(f : \{0,1\}^* \to \{0,1\}^*\) such that

1. For every \(x \in \{0,1\}^*\), we have \(x \in A \Leftrightarrow f(x) \in B\), and
2. There is a polynomial-time Turing machine \(M\) that on any input \(x \in \{0,1\}^*\), replaces it with \(f(x)\) on the tape then halts.

The polynomial-time reductions as defined above are also known as Karp reductions and polynomial-time many-to-one reductions. There are other closely related notions of reductions that can be defined, but this specific definition is useful in establishing the following basic relation between languages.

Lemma 1. For every two languages \(A, B \subseteq \{0,1\}^*\) that satisfy \(A \le_{\mathbf{P}} B\),

1. If \(B \in \mathbf{P}\), then \(A \in \mathbf{P}\) as well, and
2. If \(B \in \mathbf{NP}\), then \(A \in \mathbf{NP}\) as well.

Proof. Let \(f : \{0,1\}^* \to \{0,1\}^*\) be a function that shows \(A \le_{\mathbf{P}} B\) and let \(M_f\) be a polynomial-time Turing machine that replaces \(x\) with \(f(x)\) on the tape in polynomial time.

Consider the case where \(B \in \mathbf{P}\) and is decided by the polynomial-time Turing machine \(M_B\). We can decide \(A\) with the following simple algorithm. On input \(x\), we run \(M_f\) to replace it with \(f(x)\). Then we simulate \(M_B\). The resulting algorithm decides \(A\) since \(x \in A \Leftrightarrow f(x) \in B\). And it can be implemented with a polynomial-time Turing machine since both \(M_f\) and \(M_B\) have polynomial time cost. So \(A \in \mathbf{P}\).

When \(B \in \mathbf{NP}\), the proof that \(A \in \mathbf{NP}\) as well is nearly identical. The only difference is that we verify \(A\) by running \(M_f\) and then simulate the polynomial-time verifier \(V_B\) for \(B\). Then for any \(x \in \{0,1\}^*\), there is a certificate \(c\) that causes this verifier to accept \((x,c)\) if and only if the certificate \(c\) causes \(V_B\) to accept \((f(x),c)\), so \(x\) is accepted if and only if \(f(x) \in B \Leftrightarrow x \in A\).

Note that the lemma also implies the contrapositive statements: when \(A \le_{\mathbf{P}} B\), if \(A \notin \mathbf{P}\) then \(B \notin \mathbf{P}\) either, and the same is true for \(\mathbf{NP}\) as well. Both the direct and contrapositive forms of Lemma 1 will prove to be useful.

Using reductions, we can identify the “hardest” problems in \(\mathbf{NP}\).

Definition. The language \(L\) is \(\mathbf{NP}\)-hard if every language \(A \in \mathbf{NP}\) satisfies \(A \le_{\mathbf{P}} L\).

The language \(L\) is \(\mathbf{NP}\)-complete if \(L \in \mathbf{NP}\) and \(L\) is \(\mathbf{NP}\)-hard.

Is it possible for a language to be both \(\mathbf{NP}\)-complete and in \(\mathbf{P}\)? Possibly, but only if \(\mathbf{P} = \mathbf{NP}\)!

Proposition. If any \(\mathbf{NP}\)-hard language \(L\) is in \(\mathbf{P}\), then \(\mathbf{P} = \mathbf{NP}\).

Or, equivalently, if \(\mathbf{P} \neq \mathbf{NP}\) and \(L\) is \(\mathbf{NP}\)-hard, then \(L \notin \mathbf{P}\).

Proof. Let \(L\) be an \(\mathbf{NP}\)-hard language that is in \(\mathbf{P}\).

Fix any \(A \in \mathbf{NP}\). By the definition of \(\mathbf{NP}\)-hardness, \(A \le_{\mathbf{P}} L\). And by Lemma 1, \(L \in \mathbf{P}\) implies that \(A \in \mathbf{P}\) as well.

First NP-Complete Language

Here’s a simple challenge: Can you prove that there exists an \(\mathbf{NP}\)-complete language?

Now there’s a word in the question above that should raise some eyebrows. That’s a simple challenge? If you have already seen the famous (and justifiably so!) Cook-Levin Theorem before, you would certainly be right in observing that the theorem is far from a solution to “a simple challenge”. But there is an important distinction: the Cook-Levin Theorem does more than just show that there exists an \(\mathbf{NP}\)-complete language exists, it shows that the natural Satisfiability problem is \(\mathbf{NP}\)-complete.

If we only aim to establish the \(\mathbf{NP}\)-completeness of an arbitrary language, our task is much easier.

Proposition. There exists an \(\mathbf{NP}\)-complete language.

Proof. Consider the language \(A_{TM}^{cert}\) of all strings \(\left< M \right> x 0^m 1^t\) where there exists a certificate \(c\) of length \(|c| \le m\) such that \(M\) accepts \((x,c)\) after at most \(t\) computation steps.

Our first task is to show that \(A_{TM}^{cert}\) is in \(\mathbf{NP}\). Let \(V\) be a verifier that simulates at most \(t\) transitions of \(M\) using its own certificate as \(c\). The check that the certificate \(c\) has length at most \(m\) and the simulation of \(t\) steps of \(M\) can both be completed in polynomial time. And \(V\) accepts if and only if there is a certificate \(c\) of length \(|c| \le m\) that causes \(M\) to accept \(x\) within at most \(t\) steps, so it indeed is a polynomial-time verifier for \(A_{TM}^{cert}\).

Now we want to show that \(A_{TM}^{cert}\) is \(\mathbf{NP}\)-hard. Fix any language \(L \in \mathbf{NP}\). This means that there exist polynomials \(p\) and \(q\) and a verifier \(V\) such that for every \(x \in \{0,1\}^n\),

1. If \(x \in L\), there exists \(u \in \{0,1\}^{p(n)}\) that causes \(V\) to accept \((x,u)\);
2. If \(x \notin L\), every possible \(u \in \{0,1\}^{p(n)}\) causes \(V\) to reject \((x,u)\); and
3. \(V\) has time cost \(q(n)\).

Define \(f : x \mapsto \left< V \right> x 0^{p(|x|)} 1^{q(|x|)}\). The function \(f\) can be computed by a polynomial-time Turing machine and satisfies the condition that \(x \in L\) if and only if \(f(x) \in A_{TM}^{cert}\), so \(L \le_{\mathbf{P}} A_{TM}^{cert}\).

Eric Blais ©2024 — Last edited on Feb. 2, 2024