Section 1.5 NP-hard and NP-complete Problems
As we discussed in Section 1.4, a powerful idea in computational complexity is the notion of a reduction; i.e. showing that one problem can be converted into another in polynomial time. Since the “reduces to” relation is transitive and reflexive, it naturally leads to equivalence classes among problems and a partial order on those equivalence classes. As is usually the case when dealing with equivalence classes, it can be valuable to be able to identify an equivalence class with a “representative”. This leads us to the notion of the “hard” and “complete” problems for a class.
To be clear, when we speak about a “complexity class” we do not necessarily mean an equivalence class in the equivalence relation that we have described above. For example, NP itself is probably not an equivalence class because, if \(\text{P}\neq\text{NP}\text{,}\) then there are problems in this class that cannot be reduced to others. However, NP will be considered to be a complexity class for the sake of this reduction. Roughly speaking, usually, when we speak about complexity classes, we are referring to a subset of equivalence classes which is “downward closed” in the poset meaning that if a problem is in the class, then all problems that can be reduced to it (i.e. all “easier” problems) are also in the class. This informal definition of a complexity class is perhaps not fully rigorous but should be good enough for this course.
Definition 1.5.2.
Let \(\mathcal{C}\) be a complexity class. A problem \(X\) is said to be complete for \(\mathcal{C}\text{,}\) or \(\mathcal{C}\)-complete, if \(X\in\mathcal{C}\) and \(X\) is \(\mathcal{C}\)-hard.In other words, a problem is hard for \(\mathcal{C}\) if any algorithm for solving \(X\) could also be used to solve any problem in \(\mathcal{C}\) with only a polynomial loss in efficiency. If \(X\) is additionally a member of \(\mathcal{C}\text{,}\) then it is complete for \(\mathcal{C}\text{.}\) In other words, the complete problems for a complexity class are the “hardest” problems in that class, up to polynomial reductions. In the context of NP, the original (or “OG”) complete problem is the boolean satisfiability problem (SAT).
Definition 1.5.3.
A boolean variable, say \(x\text{,}\) is a variable which can take on two possible values, say \(0\) and \(1\text{,}\) where \(0\) represents false and \(1\) represents true. A literal is a boolean variable or its negation. A boolean formula is a function \(f(x_1,\dots,x_n)\) of boolean variables \(x_1,\dots,x_n\) obtained from those variables using the standard boolean operations of \(\land\) (and), \(\lor\) (or) and \(\neg\) (not).Definition 1.5.4.
A boolean formula \(f(x_1,\dots,x_n)\) is satisfiable if there exists a choice of the values of the variables \(x_1,\dots,x_n\) such that the formula outputs \(1\text{.}\) Otherwise, it is unsatisfiable.
Problem 1.5.5. The Satisfiability Problem (SAT).
- Input: A boolean formula \(f(x_1,\dots,x_n)\text{.}\)
- Question: Is \(f\) satisfiable?
It is evident that SAT is in NP since, if someone hands you a purported choice of variables which satisfies the formula (i.e. a satisfying assignment), then it is not hard to just apply the logical operations to check whether it ends up evaluating to \(0\) or \(1\text{.}\) What is not so obvious at first (but becomes a bit clearer after a bit of thinking; see below) is that SAT is NP-complete; that is, every problem in NP can be reduced to SAT. In fact, SAT was the first ever example of an NP-complete problem, and this fact is known as the Cook–Levin Theorem.
Theorem 1.5.6. The Cook–Levin Theorem.
SAT is NP-complete.We will not formally prove this theorem because it would require us to build up a theoretical framework that would feel like overkill for a course like this, and is not necessary for building intuition. Instead, let us just talk informally about how a reduction from a problem in NP to SAT would typically work. Given that a problem \(X\) is in NP, we know that there is a polynomial time procedure for verifying a certificate for a yes instance of \(X\text{.}\) The trick to proving the Cook–Levin theorem is to encode the procedure for verifying a certificate as a SAT formula, and so the formula will be satisfiable if and only if there is a yes certificate for the instance of problem \(X\text{.}\) Since the verification of a certificate can be done in polynomial time, the size of the SAT formula will also be a polynomial in the size of any given instance of \(X\text{.}\)
To see how this works in practice, let us think about the 3-Colourability Problem (Problem 1.4.3). We start with any instance \(G\) for the 3-Colourability Problem and would like to convert it into an instance of the SAT Problem. In general, when doing this for any problem in NP, the key idea is to think about the algorithm that one would use to verify a yes certificate, and try to build a SAT formula which simulates that procedure. For 3-colourability, a certificate is a proper \(3\)-colouring of the graph; that is, a mapping \(f:V(G)\to\{1,2,3\}\) where adjacent vertices get different colours. Before we start to encode the algorithm for checking validity of such a certificate into our boolean formula, we first need to build up some structure to encode “what” the certificate is. For this, we introduce, for each vertex \(v\in V(G)\text{,}\) three boolean variables \(x_{v,1},x_{v,2}\) and \(x_{v,3}\) where, for \(i\in \{1,2,3\}\text{,}\) the statement \(f(v)=i\) will be represented by the variable \(x_{v,i}\) being equal to \(1\) (i.e. true). In a certificate, every vertex must be mapped to one of the numbers \(1,2\) or \(3\text{,}\) and so our formula should only evaluate to true if all formulas of the following type evaluate to true:
\begin{equation*}
x_{v,1}\lor x_{v,2}\lor x_{v,3}\quad\text{for }v\in V(G).
\end{equation*}
Thus, the starting point for our SAT formula is
\begin{equation*}
\bigwedge_{v\in V(G)}\left(x_{v,1}\lor x_{v,2}\lor x_{v,3}\right).
\end{equation*}
Note that, technically, this only ensures that at least one of \(x_{v,1}, x_{v,2}\) or \(x_{v,3}\) is true, but, in the 3-Colourability Problem, a natural certificate only has one of these variables being true. If you wanted, you could add additional structure to the SAT instance to force exactly one of them to be true, but this turns out to be unnecessary. Next, let us think about how we would verify a certificate. The most natural way to do this is to go through each edge of the graph, one by one, and check that its endpoints have different colours. In the context of our SAT formula, this means checking that \(\neg x_{u,i}\lor \neg x_{v,i}\) is true for every edge \(uv\in E(G)\) and every \(i\in\{1,2,3\}\text{.}\) So, we augment our formula to the following:
\begin{equation*}
\left(\bigwedge_{v\in V(G)}\left(x_{v,1}\lor x_{v,2}\lor x_{v,3}\right)\right)\land\left(\bigwedge_{uv\in E(G)}\bigwedge_{i\in\{1,2,3\}} \left(\neg x_{u,i}\lor \neg x_{v,i}\right)\right).
\end{equation*}
And that’s it; we have successfully reduced 3-Colourability to SAT. Note that this reduction can clearly be carried out in polynomial time. To recap, the key steps were to (1) encode the “meaning” of a certificate into a boolean formula, (2) encode the procedure for checking the validity of a cerficate into a boolean formula and (3) connect the two with an \(\land\) symbol. To prove the Cook–Levin Theorem, all that one needs to do is to exploit the definition of NP to show that any problem in NP can be reduced to SAT by following this basic recipe.
Now that we have one example of an NP-complete problem, there is a natural way to build up additional NP-complete and NP-hard problems from it. For any problem \(X\text{,}\) if we want to show that \(X\) is NP-hard, then it suffices to obtain a reduction from SAT (or any other NP-hard problem) to \(X\text{.}\) The instances of SAT are all possible boolean formulas, which can be a bit cumbersome to deal with. For this reason, it is useful to reduce SAT to a variant of SAT with more restricted inputs. Being able to deal with a restricted version of SAT will be valuable for NP-hardness reductions because, rather than needing to “simulate” every possible boolean formula with a reduction, we will only need to simulate a restricted family of well-structured boolean formulas. To explain this, we need to discuss two standard classes of boolean formulas.
Definition 1.5.7.
A boolean formula is in disjunctive normal form (DNF) if it is expressed as a disjunction (i.e. an “or”) of one or more conjunctions (i.e. an “and”) of literals.Definition 1.5.8.
A boolean formula is in conjunctive normal form (CNF) if it is expressed as a conjunction (i.e. an “and”) of one or more disjunctions (i.e. an “or”) of literals.It is perhaps best to explain these two notions by way of example. A DNF formula involves creating a bunch of formulas using literals (i.e. variables or their negations) connected by \(\land\) symbols and then connecting all of these formulas with \(\lor\) symbols. For example, the following is a DNF formula:
\begin{equation*}
(x_1\land \neg x_2)\lor (\neg x_1\land x_2\land \neg x_3)\lor x_3\lor (\neg x_1\land \neg x_3).
\end{equation*}
Clearly, the above formula is satisfiable. In fact, all of the satisfying assignments for this formula can be simply “read out” from the formula itself. That is, it will evaluate to true if and only if \((x_1,x_2)=(1,0)\text{,}\) \((x_1,x_2,x_3)=(0,1,0)\text{,}\) \(x_3=1\) or \((x_1,x_3)=(0,0)\text{.}\) In general, it is super easy to check whether a DNF formula is satisfiable. The only way for such a formula to fail to be satisfiable is if every conjunction in the definition of the formula contains a literal and its negation. For example, this is an example of a DNF formula that is not satisfiable.
\begin{equation*}
(x_1\land \neg x_1)\lor (\neg x_1\land x_3\land \neg x_3).
\end{equation*}
In contrast, a CNF formula is obtained by creating a bunch of formulas involving literals connected by \(\lor\) symbols (called clauses) and then connecting all of the clauses with \(\land\) symbols. For example,
\begin{equation*}
(x_1\lor \neg x_2)\land (\neg x_1\lor x_2\lor \neg x_3)\land x_3\land (\neg x_1\lor \neg x_3)
\end{equation*}
is a CNF. In this example, it turns out that there is a unique satisfying assignment and it is not too hard to find it (start with the clause \(x_3\) and see where it leads you). However, in contrast to DNFs, it is generally not at all straightforward to determine whether a CNF is satisfiable, especially if the number of clauses is large and the number of literals in each clause is not too small. A standard restriction of the SAT Problem is to SAT Problems for CNF inputs with clauses of bounded size.
Problem 1.5.9. The \(k\)-Satisfiability Problem (\(k\)-SAT).
- Input: A boolean formula in CNF with at most \(k\) literals in each clause.
- Question: Is \(f\) satisfiable?
As an aside, we remark that our reduction of 3-Colourability to SAT actually constructed, for each instance of 3-Colourability, an instance of 3-SAT. So, in fact, 3-Colourability reduces to 3-SAT. However, since we do not yet know that 3-Colourability is NP-hard (it is, but we haven’t proven it), this observation does not have much utility for us right now!
If we would like to reduce SAT to 3-SAT, then we first need a way to transform an instance of SAT into an instance of SAT that is in CNF (i.e. an instance of the CNF-SAT Problem). We already need to be careful in this step. As it turns out, if you simply try to convert a boolean formula into a CNF that is equivalent (i.e. has the same variables and the same truth value for every assignment of variables), then, in general, it may be the case that every such CNF has exponential size; see Exercise 20. To convert an instance of SAT into an instance of CNF-SAT in polynomial time, it turns out that it is useful to actually increase the number of variables to create a new formula that is satisfiable if and only if the original is satisfiable (where the two are not technically equivalent because they have different variables). This approach is known as a Tseytin transformation. Again, we will avoid getting bogged down with the formalism required to explain this in full generality and just analyze one example. consider the formula
\begin{equation*}
\neg\left(x_1\land x_2\right)\lor\left(x_3\land x_4\right).
\end{equation*}
Let us work our way from the “inside out.” We start with the expression \(x_1\land x_2\text{.}\) We introduce a new variable \(y_1\) and consider the expression
\begin{equation*}
\left(\neg x_1\lor \neg x_2\lor y_1\right)\land \left( x_1\lor \neg y_1\right)\land \left(x_2\lor \neg y_1\right).
\end{equation*}
Importantly, this expression is in CNF and, if you think through it, you will see that, in every satisfying assignment of the above formula involving \(x_1,x_2\) and \(y_1\text{,}\) the variable \(y_1\) has the same truth value as \(x_1\land x_2\text{.}\) Thus, if we insist that this formula is satisfied (using a conjunction), then we are free to “substitute” \(y_1\) in for \(x_1\land x_2\) without changing the satisfiability of the formula. That is, our original formula is satisfiable if and only if the formula
\begin{equation*}
\left(\neg y_1\lor\left(x_3\land x_4\right)\right)\land\left(\neg x_1\lor \neg x_2\lor y_1\right)\land \left( x_1\lor \neg y_1\right)\land \left(x_2\lor \neg y_1\right)
\end{equation*}
is satisfiable. Now, if we do the same thing to \(x_3\land x_4\text{,}\) we will end up with a CNF. The transformation that we used here belongs to a larger family that can also deal with other boolean operations. Our main point here is that, starting with any boolean formula, we can get another formula in CNF that is satisfiable if and only if the original is satisfiable and this can be done in polynomial (in fact, linear) time.
Okay, so SAT can be reduced to CNF-SAT which means that the latter is also NP-complete. As it turns out, there is an even simpler trick for reducing CNF-SAT to 3-SAT. To see this, suppose that we have a CNF formula containing a large clause, such as
\begin{equation*}
x_1\lor x_2\lor \cdots \lor x_k.
\end{equation*}
Our goal now is to “split off” the first two literals into their own clause and add a new variable, say \(y_{1,2}\text{,}\) for the purposes of “communicating” between the new clause and another clause consisting of all other variables. That is, we replace our original clause with
\begin{equation*}
\left(x_1\lor x_2\lor y_{1,2}\right)\land\left(\neg y_{1,2}\lor x_3\lor \cdots \lor x_k\right).
\end{equation*}
Note that this has not ruined the CNF structure and it has replaced one clause of \(k\) literals with two clauses, one with \(3\) literals and another with \(k-1\) literals. Also, note that making this replacement does not affect the satisfiability of the original formula from which this clause came. Indeed, if the original clause is satisfiable, then one of the literals \(x_1,\dots,x_k\) must be true. So, at least one of the sets \(\{x_1,x_2\}\) or \(\{x_3,\dots,x_k\}\) contains a true literal and we can use the variable \(y_{1,2}\) to cause the other clause to be true as well. On the other hand, if the formula is not satisfiable, then, in every assignment of variables, either one of the other clauses is false or the clause \(x_1\lor \cdots\lor x_k\) is false. In the latter case, this means that none of these variables are true and so at least one of our new clauses must be false, regardless of the value of \(y_{1,2}\text{.}\) Repeating this for every clause of length greater than three until none exist yields an instance of 3-SAT. Thus, we have the following.
Theorem 1.5.10. Karp.
3-SAT is NP-complete.This theorem was first proven in a legendary paper of Karp in which he obtained a list consisting of 21 examples of NP-complete problems. These include the Hamiltonian Cycle Problem (Problem 1.4.5), the Stable Set and Clique Problems introduced in Exercise 13, the Vertex Cover Problem that is intimately linked with matching problems studied in Chapter 3, the 3-Colourability Problem (Problem 1.4.3) and various related graph colouring problems that are the focus of Chapter 4 and the Max-Cut Problem that we study in Section 7.2. As you can probably tell from this list, many problems of theoretical and practical interest are, unfortunately, NP-complete. We should also point out that the study of classifying problems based on their complexity is an ongoing area of research and there are many problems, including very natural ones, for which the precise complexity is not known; a famous example is the Graph Isomorphism Problem discussed in Exercise 7.
Our discussion here has been mostly focused on NP-complete problems, but it is worth saying a few words about NP-hard problems. The class of NP-hard problems contains the set of NP-complete problems, by definition. An NP-hard problem can only fail to be NP-complete if it is not contained within NP. For a decision problem, saying that it is NP-hard but not NP-complete is quite a strong statement since it asserts that there is no polynomial-time checkable certificate for a yes-instance to the problem. However, there is also another context in which we often speak about problems being NP-hard but not NP-complete. If we have a problem \(X\) which is not a decision problem—for example, an optimization problem—we will often use the term NP-hard to mean that any problem in NP can be reduced to solving an instance of \(X\text{,}\) but \(X\) itself is not in NP because it is not even a decision problem. This may seem like somewhat of a technicality, but it is worth remembering that every element of NP is a decision problem, and so optimization problems cannot be in NP. The problem of computing the chromatic number or largest cardinality of a clique in a graph are examples of problems that are NP-hard but cannot be called NP-complete because they are not decision problems. More generally, the integer linear programming problems that we discuss in Chapter 6 also fall into this category.
Here is a YouTube video related to the topics of this section.
