$\mathbf{NP}$-completeness
Recall that reduction is not symmetric. This suggests that one thing we could do is try to find the "hardest" problems in NP and try to separate those from the "easier" ones. But what does "hardest" mean in this context? That would be the existence of some problem $A$ for which $A \leq_P B$ for all $B \in NP$. Such problems are called NP-complete.
A problem $P$ is said to be $\mathbf{NP}$-complete if
- $P \in \mathbf{NP}$, and
- for all problems $P' \in \mathbf{NP}$, $P' \leq_P P$.
If a problem $P$ satisfies (2), we say $P$ is $\mathbf{NP}$-hard.
It's important to note that a problem can be $\mathbf{NP}$-hard but not in $\mathbf{NP}$, which is why that notion is separate from the notion of completeness. Problems that are $\mathbf{NP}$-complete represent the "most difficult" problems in $\mathbf{NP}$.
One consequence of the existence of such a problem is it would give us a very easy way to show that $\mathbf{NP} = \mathbf P$. Suppose that $P$ is $\mathbf{NP}$-complete. If we find a polynomial time algorithm for $P$, then this means we have a polynomial time algorithm for every problem in $\mathbf{NP}$, by transitivity of $\leq_P$, and therefore $\mathbf P = \mathbf{NP}$.
Of course, an obvious question is whether such a problem exists. It sounds like a lot of work to show that a problem $P$ is $\mathbf{NP}$-complete, since one would have to show how to encode an arbitrary problem in $\mathbf{NP}$ into an instance of $P$ (how would this work for something like Vertex Cover?). But for now, let's suppose that there is an $\mathbf{NP}$-complete problem out there. By using transitivity of $\leq_P$, we get the following.
Let $P$ be $\mathbf{NP}$-complete and suppose $P' \in \mathbf{NP}$. If $P \leq_P P'$ then $P'$ is $\mathbf{NP}$-complete.
Let $Q \in \mathbf{NP}$. Since $P$ is $\mathbf{NP}$-complete, we have $Q \leq_P P$. But since $P \leq_P P'$, by transitivity, we have $Q \leq_P P'$. Since $Q$ was arbitrary, we have that $P'$ is $\mathbf{NP}$-complete.
So if we want to show that $P$ is $\mathbf{NP}$-complete, we can avoid having to show how to transform an instance of some arbitrary problem in $\mathbf{NP}$ into an instance of $P$. All we have to do is show that we can transform a problem we've already shown is $\mathbf{NP}$-complete into $P$, which is much easier. The other observation is that this means that all $\mathbf{NP}$-complete problems are polynomial time reducible to each other.
Of course, all of this only works if such a problem actually exists. That such a problem does exist was shown in 1971 by Stephen Cook, who we've seen before briefly when we were discussing fast integer multiplication. This is the result for which Cook is most famous. The theorem was independently proved by Leonid Levin, who at the time was in the Soviet Union. Levin is currently a faculty member at Boston University and Cook is a faculty member at the University of Toronto, which he joined in 1970 due to being denied tenure at Berkeley.
Satisfiability is $\mathbf{NP}$-complete.
One thing you might notice is that $\mathbf{NP}$ is not exactly an acronym for polynomially verifiable. That is because efficient verification is an alternate, but equivalent, definition for $\mathbf{NP}$. $\mathbf{NP}$ actually stands for nondeterministic polynomial time. The original definition has to do with distinguishing between problems that could be solved on deterministic vs. nondeterministic Turing machines.
For our purposes, we can think of it this way: we can solve a problem in $\mathbf{NP}$ in polynomial time using nondeterminism. How do we do this? First, we nondeterministically guess/choose a certificate $c$. Since $c$ is polynomial in size, we can do this in polynomial time. Then once we have our string, we can run the verifier in polynomial time to get our answer.
We won't go through the proof in detail here, because it involves Turing machines, but the proof is really amazing. So recall that a Turing machine is a model of computation and for all intents and purposes, you can consider a specific Turing machine as a computational device that computes the solution to a particular problem, much like an algorithm. Here, we're particularly interested in nondeterministic Turing machines.
Since $\mathbf{NP}$ is the class of problems that can be solved by a nondeterministic Turing machine in polynomial time, an easy way to show that every problem reduces to a particular problem is just to show how to simulate a nondeterministic Turing machine. This is basically what the proof of Cook-Levin does.
The idea is to take a nondeterministic Turing machine and an input string and to show how to construct a propositional formula that simulates the computation of the Turing machine on the input string. The proof involves showing the following:
- the constructed propositional formula has a satisfying assignment if and only if the Turing machine outputs Yes on the input string, and
- the constructed propositional formula is of size polynomial in the size of the input string.
The consequence of this is that if we can solve Satisfiability, we can solve any problem in $\mathbf{NP}$. How? Here is an algorithm:
- Suppose you're given a nondeterministic Turing machine $M$ and an input string $x$. Construct a propositional formula $\varphi_{M,x}$ in polynomial time and of polynomial size according to Cook-Levin.
- Solve Satisfiability on $\varphi_{M,x}$.
- If the answer is Yes, then $\varphi_{M,x}$ is satisfiable, and therefore $M$ answers Yes on $x$. If the answer is No, then $\varphi_{M,x}$ is satisfiable, and therefore $M$ answers No on $x$.
So if we can solve Satisfiability in polynomial time, we can solve any problem in $\mathbf{NP}$ in polynomial time.
The existence of an NP-complete problem was obviously a huge breakthrough and the natural follow-up question was what other NP-complete problems might be out there. Since these are the hardest problems in NP, the thinking was that we'd find a few more and it wouldn't be very long before we're able to show a clear separation from P. Not long after, Richard Karp (from Edmonds-Karp) published a paper showing 21 problems were NP-complete in 1972, some of which we've seen already. And since Cook-Levin and Karp, there have been thousands of problems shown to be $\mathbf{NP}$-complete.
Practically speaking, this gives us a much easier way to prove that certain problems are $\mathbf{NP}$-complete (which, for now, means that we can give up on finding an efficient algorithm for them). To do this we need to show that our problem is in $\mathbf{NP}$ and that there is an $\mathbf{NP}$-complete problem that reduces to it. This can be summarized in four steps.
To prove that a problem $A$ is $\mathbf{NP}$-complete,
- Show that $A \in \mathbf{NP}$. In other words, describe how to verify Yes instances of $A$ in polynomial time, by describing an appropriate certificate and how you would verify it.
- Choose a problem $B$ that you already know is $\mathbf{NP}$-complete.
- Describe how to map Yes instances of $B$ to Yes instances of $A$.
- Show that your mapping can be computed in polynomial time.
Let's try this out.
Satisfiability $\leq_P$ 3-SAT.
We need to transform an arbitrary boolean formula $\varphi$ into one that is in CNF and has at most three literals per clause. To do this, we will go through a series of transformations, each of which preserves the truth of the original formula.
First, we will parenthesize the formula into what is sometimes called a well-formed formula. Essentially, this means rewriting the formula so that the order of operations are explicitly defined by the parentheses. It is clear that this rewriting doesn't change the formula.
Once we have such a formula, we can very easily construct a parse tree for the formula. For example, for the formula $\varphi = (((x_1 \to x_2) \wedge (x_3 \wedge \neg x_1)) \vee (x_2 \to \neg x_4)) \vee x_3$, we have the following parse tree.
We observe that in such a tree, the leaves are all literals and the internal nodes of the tree are all connectives. We observe that every connective has exactly two children. What we will do is, for each connective $(x \circ y)$, construct a clause $(z \leftrightarrow x \circ y)$, where $z$ is a new variable and replace the subformula with $z$. Since all connectives are binary, we have a set of clauses with three literals of the form $(z \leftrightarrow x \circ y)$.
For each of these clauses, we can rewrite them using only $\vee$ and $\wedge$ by using a truth table and writing the result in disjunctive normal form (ors of ands). Since all of our clauses are of the form $C = (z \leftrightarrow (x \circ y))$, we have a truth table
| $x$ | $y$ | $z$ | $C$
|
|---|
| T | T | T | ?
|
| T | T | F | ?
|
| T | F | T | ?
|
| T | F | F | ?
|
| F | T | T | ?
|
| F | T | F | ?
|
| F | F | T | ?
|
| F | F | F | ?
|
Then we can construct a formula in disjunctive normal form for $\neg C$ by taking each row that evaluates to $F$, $\wedge$ing the variables together and $\vee$ing those clauses.
For example, suppose $C = (z \leftrightarrow (x \wedge \neg y))$. Then
| $x$ | $y$ | $z$ | $(z \leftrightarrow (x \wedge y))$
|
|---|
| T | T | T | T
|
| T | T | F | F
|
| T | F | T | F
|
| T | F | F | T
|
| F | T | T | F
|
| F | T | F | T
|
| F | F | T | F
|
| F | F | F | T
|
This gives us the formula
\[\neg C = (x \wedge y \wedge \neg z) \vee (x \wedge \neg y \wedge z) \vee (\neg x \wedge y \wedge z) \vee (\neg x \wedge \neg y \wedge z).\]
We then apply De Morgan's laws on our formula for $\neg C$ to turn the result into a formula for $C$ in conjunctive normal form. Again, this does not change the satisfiability of the formula.
This leaves us with clauses with three, two, or one literals. We can stuff the clauses with only one or two literals with dummy variables as follows:
- if we have a clause $(x_1 \vee x_2)$, replace it with $(x_1 \vee x_2 \vee p) \wedge (x_1 \vee x_2 \vee \neg p)$;
- if we have a clause $(x_1)$, replace it with $(x_1 \vee p \vee q) \wedge (x_1 \vee \neg p \vee q) \wedge (x_1 \vee p \vee \neg q) \wedge (x_1 \vee \neg p \vee \neg q)$;
where $p$ and $q$ are new variables. We use the same variables $p$ and $q$ for all clauses that need them. It is clear that adding these variables does not affect the satisfiability of the formula.
It remains to show that the construction can be done in polynomial time. It is clear that parenthesizing the formula can be done in one pass of the formula. Then what is the size of the parse tree? This looks like it could be exponential, but it's actually linear in the length of the formula: every node corresponds to either a literal or a connective in the formula. This is important, because we use the parse tree as the basis of our transformation.
Roughly speaking, we define a clause for each connective in our parse tree. This corresponds to one clause per internal node of the parse tree, which is linear in the length of the formula. Each clause increases the size of the instance by a constant amount. Then rewriting each clause also requires a constant amount of time and space: in the very worst case, we get a formula of eight clauses in DNF per clause we start out with.
In total, performing this transformation only increases the size of the formula linearly in the length of the original formula.
3-SAT is $\mathbf{NP}$-complete.
First, we need to show that 3-SAT is in $\mathbf{NP}$. An appropriate certificate for 3-SAT is an assignment of variables. This is a list $(x_1, x_2, \dots, x_n) = (T,F,T,\dots,F)$. We can then test each clause to see if it evaluates to $T$ or $F$. If all clauses evaluate to $T$, then our formula is satisfied by the given assignment. Otherwise, it isn't. The certificate is linear in the number of variables in the formula. This is clearly verifiable in polynomial time.
By Theorem 24.4, we have that Satisfiability $\leq_P$ 3-SAT. By Theorem 24.3, Satisfiability is $\mathbf{NP}$-complete. Therefore, 3-SAT is $\mathbf{NP}$-complete.
Then it is not too hard to see that by our previous reductions and a quick argument about how they can be efficiently verified, we also have that Independent Set, Vertex Cover, and Set Cover are all $\mathbf{NP}$-complete.
One question you might have is what about 4-SAT? That is probably not a question you have, but we can see that we can turn any 3-SAT formula into a 4-SAT formula by doing our dummy variable trick. The other question is what about 2-SAT?
It turns out 2-SAT is in $\mathbf P$! This was first shown by Krom in 1967. Intuitively, the reason for this is that since every clause is of the form $(x \vee y)$, what you can do is start setting variables and seeing what you get.
For example, if $x$ is set to True, then we're done, but if $x$ is False, in order for the clause to be True, $y$ must be True. Following this chain of implications is easy when you only have two literals per clause, since you have only one possibility and you can keep on going until you get a satisfying assignment or you get stuck. If you have three literals per clause, you get two possibilities and your choices start looking like a tree, leading to exponential blowup.
We immediately get the following.
The following problems are $\mathbf{NP}$-complete:
- Independent Set
- Vertex Cover
By Proposition 24.2, if $A$ is $\mathbf{NP}$-complete, and $A \leq_P B$, and $B \in \mathbf{NP}$, then $B$ is $\mathbf{NP}$-complete. Therefore, it suffices to show that each of the problems is in $\mathbf{NP}$ and there exists a reduction from an $\mathbf{NP}$-complete problem. By Theorem 24.5, Satisfiability is $\mathbf{NP}$-complete.
- Independent Set is in $\mathbf{NP}$ by Proposition 23.13. We have 3-SAT $\leq_P$ Independent Set by Theorem 23.4 and 3-SAT is $\mathbf{NP}$-complete by Theorem 24.5. Therefore, Independent Set is $\mathbf{NP}$-complete.
- Vertex Cover is in $\mathbf{NP}$ by Proposition 23.13. We have Independent Set $\leq_P$ Vertex Cover by Proposition 22.10 and Independent Set is $\mathbf{NP}$-complete by Theorem 24.6(a). Therefore, Vertex Cover is $\mathbf{NP}$-complete.