## 9.4 The Theory of NP It is more convenient to develop the theory if we originally restrict ourselves to *decision problems.* Recall that the output of a decision problem is a simple "yes" or "no" answer. Yet when we introduced (in [Chapters 3](LiB0024.html#252), [4](LiB0032.html#359), [5](LiB0039.html#471), and [6](LiB0047.html#565)) some of the problems mentioned previously, we presented them as optimization problems, which means that the output is an optimal solution. Each optimization problem, however, has a corresponding decision problem, as the examples that follow illustrate. Example 9.2 Traveling Salesperson Problem****Let a weighted, directed graph be given. Recall that a ***tour*** in such a graph is a path that starts at one vertex, ends at that vertex, and visits all the other vertices in the graph exactly once, and that the ***Traveling Salesperson Optimization problem*** is to determine a tour with minimal total weight on its edges. The ***Traveling Salesperson Decision problem is*** to determine for a given positive number *d* whether there is a tour having total weight no greater than *d*. This problem has the same parameters as the Traveling Salesperson Optimization problem plus the additional parameter *d*. **** Example 9.3 0–1 Knapsack Problem****Recall that the ***0–1 Knapsack Optimization problem*** is to determine the maximum total profit of the items that can be placed in a knapsack given that each item has a weight and a profit, and that there is a maximum total weight *W* that can be carried in the sack. The ***0–1 Knapsack Decision problem*** is to determine, for a given profit *P*, whether it is possible to load the knapsack so as to keep the total weight no greater than *W*, while making the total profit at least equal to *P.* This problem has the same parameters as the 0–1 Knapsack Optimization problem plus the additional parameter *P.* **** Example 9.4 Graph–Coloring Problem****The ***Graph-Coloring Optimization problem*** is to determine the minimum number of colors needed to color a graph so that no two adjacent vertices are colored the same color. That number is called the ***chromatic number*** of the graph. The ***Graph-Coloring Decision problem*** is to determine, for an integer *m*, whether there is a coloring that uses at most *m* colors and that colors no two adjacent vertices the same color. This problem has the same parameters as the Graph-Coloring Optimization problem plus the additional parameter *m.* **** Example 9.5 Clique Problem****A ***clique*** in an undirected graph *G* = (*V*, *E*) is a subset *W* of *V* such that each vertex in *W* is adjacent to all the other vertices in *W.* For the graph in [Figure 9.1](#ch09fig01), {*v*2, *v*3, *v*4} is a clique, whereas {*v*1, *v*2, *v*3} is not a clique because *v*1 is not adjacent to *v*3. A ***maximal clique*** is a clique of maximal size. The only maximal clique in the graph in [Figure 9.1](#ch09fig01) is {*v*1, *v*2, *v*4, *v*5}. The ***Clique Optimization problem*** is to determine the size of a maximal clique for a given graph. The ***Clique Decision problem*** is to determine, for a positive integer *k*, whether there is a clique containing at least *k* vertices. This problem has the same parameters as the Clique Optimization problem plus the additional parameter *k.* **** [](fig9-1_0.jpg) Figure 9.1: The maximal clique{*v*1, *v*2, *v*4, *v*5} We have not found polynomial-time algorithms for either the decision problem or the optimization problem in any of these examples. However, if we could find a polynomial-time algorithm for the optimization problem in any one of them, we would also have a polynomial-time algorithm for the corresponding decision problem. This is so because *a solution to an optimization problem produces a solution to the corresponding decision problem.* For example, if we learned that the total weight of an optimal tour for a particular instance of the Traveling Salesperson Optimization problem was 120, the answer to the corresponding decision problem would be "yes" for  and "no" otherwise. Similarly, if we learned that the optimal profit for an instance of the 0–1 Knapsack Optimization problem was $230, the answer to the corresponding decision problem would be "yes" for  and "no" otherwise. Because a polynomial-time algorithm for an optimization problem automatically produces a polynomial-time algorithm for the corresponding decision problem, we can initially develop our theory considering, only decision problems. We do this next, after which we return to optimization problems. At that time, we will see that usually we can show that an optimization problem is even more closely related to its corresponding decision problem. That is, for many decision problems (including the problems in the previous examples), it's been shown that a polynomial-time algorithm for the decision problem would yield a polynomial-time algorithm for the corresponding optimization problem. ### 9.4.1 The Sets *P* and *NP* First we consider the set of decision problems that can be solved by polynomialtime algorithms. We have the following definition. Definition *P* is the set of all decision problems that can be solved by polynomial-time algorithms. What problems are in *P*? All decision problems for which we have found polynomial-time algorithms are certainly in *P.* For example, the problem of determining whether a key is present in an array, the problem of determining whether a key is present in a sorted array, and the decision problems corresponding to the optimization problems in Chapters 3 and 4 for which we have found polynomial-time algorithms, are all in *P.* However, could some decision problem for which we have not found a polynomial-time algorithm also be in *P*? For example, could the Traveling Salesperson Decision problem be in *P*? Even though no one has ever created a polynomial-time algorithm that solves this problem, no one has ever proven that it cannot be solved with a polynomialtime algorithm. Therefore, it could *possibly* be in *P.* To know that a decision problem is not in *P*, we have to *prove* that it is not possible to develop a polynomial-time algorithm for it. This has not been done for the Traveling Salesperson Decision problem. These same considerations hold for the other decision problems in [Examples 9.2](#ch09ex02) to [Examples 9.5](#ch09ex05). What decision problems are not in *P*? Because we do not know whether the decision problems in [Examples 9.2](#ch09ex02) to [Examples 9.5](#ch09ex05) are in *P*, each of these may not be in *P.* We simply do not know. Furthermore, there are thousands of decision problems in this same category. That is, we do not know whether they are in *P.* Garey and Johnson (1979) discuss many of them. There are actually relatively few decision problems that we know for certain are not in *P.* These problems are decision problems for which we have proven that polynomial-time algorithms are not possible. We discussed such problems in [Section 9.3.2](LiB0076.html#894). As noted there, Presburger Arithmetic is one of the most well-known. Next we define a possibly broader set of decision problems that includes the problems in [Examples 9.2](#ch09ex02) to [Examples 9.5](#ch09ex05). To motivate this definition, let's first discuss the Traveling Salesperson Decision problem further. Suppose someone claimedto know that the answer to some instance of this problem was "yes." That is, the person said that, for some graph and number *d*, a tour existed in which the total weight was no greater than *d.* It would he reasonable for us to ask the person to "prove" this claim by actually producing a tour with a total weight no greater than *d.* If the person then produced something, we could write the algorithm that follows to *verify* whether what they produced was a tour with weight no greater than *d.* The input to the algorithm is the graph *G*, the distance *d*, and the string *S* that is claimed to be a tour with weight no greater than *d*. ``` bool verify (weighted_digraph G, number d, claimed_tour S) { if (S is a tour && the total weight of the edges in S is <= d) return true; else return false; } ``` This algorithm first checks to see whether *S* is indeed a tour. If it is, the algorithm then adds the weights on the tour. If the sum of the weights is no greater than *d*, it returns "true." This means that is has verified that yes, there is a tour with total weight no greater than *d*, and we know that the answer to the decision problem is "yes." If *S* is not a tour or the sum of the weights exceeds *d*, the algorithm returns "false." Returning false means only that this claimed tour is not a tour with total weight no greater than *d.* It does not mean that such a tour does not exist, because there might be a different tour with total weight no greater than *d.* It is left as an exercise to implement the algorithm more concretely and show that it is polynomial-time. This means that, given a candidate tour, we can verify in polynomial time whether this candidate proves that the answer to our decision problem is "yes". If the proposed tour turns out not to be a tour or to have total length greater than *d* (perhaps the person was bluffing), we have not proven that the answer must be "no" to our decision problem. Therefore, we are not talking about being able to verify that the answer to our decision problem is "no" in polynomial time. It is this property of polynomial-time verifiability that is possessed by the problems in the set *NP*, which we define next. This does not mean that these problems can necessarily be solved in polynomial time. When we verify that a candidate tour has total weight no greater than *d*, we are not including the time it took to find that tour. We are only saying that the verification part takes polynomial time. To state the notion of polynomial-time verifiability more concretely, we introduce the concept of a ***nondeterininistic algorithm.*** We can think of such an algorithm as being composed of the following two separate stages: 1. **Guessing (Nondeterministic) Stage:** Given an instance of a problem, this stage simply produces some string *S*. The string can be thought of as a guess at a solution to the instance. However, it could just be a string of nonsense. 2. **Verification (Deterministic) Stage:** The instance and the string *S* are the input to this stage. This stage then proceeds in an ordinary deterministic manner either (1) eventually halting with an output of "true," which means that it has been verified that the answer for this instance is "yes," (2) halting with an output of "false," or (3) not halting at all (that is, going into an infinite loop). In these latter two cases, it has not been verified that the answer for this instance is "yes." As we shall see, for our purposes these two cases are indistinguishable. Function *verify* does the verification stage for the Traveling Salesperson Decision problem. Notice that it is an ordinary deterministic algorithm. It is the guessing stage that is nondeterministic. This stage is called ***nondeterministic*** because unique step-by-step instructions are not specified for it. Rather, in this stage, the machine is allowed to produce any string in an arbitrary matter. A "nondeterministic stage" is simply a definitional device for the purpose of obtaining the notion of polynomial-time verifiability. It is not a realistic method for solving a decision problem. Even though we never actually use a nondeterministic algorithm to solve a problem, we say that a nondeterministic algorithm "solves" a decision problem if: 1. For any instance for which the answer is "yes," there is some string *S* for which the verification stage returns "true". 2. For any instance for which the answer is "no," there is no string for which the verification stage returns "true". The following table shows the results of some input strings *S* to function verify when the instance is the graph in [Figure 9.2](#ch09fig02) and *d* is 15. [](fig9-2_0.jpg) Figure 9.2: The tour \[*v*1, *v*3, *v*2, *v*4, *v*1\] has total weight no greater than 15. S Output Reason \[*v*1, *v*2, *v*3, *v*4, *v*1\] False Total weight is greater than 15 \[*v*1, *v*4, *v*2, *v*3, *v*1\] False *S* is not a tour \#α12\*&%a1 / False *S* is not a tour \[*v*1, *v*3, *v*2, *v*4, *v*1\] True *S* is a tour with total weight no greater than 15 The third input illustrates that *S* can just be a string of nonsense (as discussed previously). In general, if the answer for a particular instance is "yes," function verify returns "true" when one of the tours with total weight no greater than *d* isthe input. Therefore, Criterion 1 for a nondeterministic algorithm is satisfied. On the other hand, function *verify* only returns "true" when a tour with total weight no greater than *d* is the input. Therefore, if the answer for an instance is "no," function *verify* does not return "true" for any value of *S*, which means that Criterion 2 is satisfied. A nondeterministic algorithm that simply generates strings in the guessing state and calls function *verify* in the verification stage therefore "solves" the Traveling Salespersoh Decision problem. Next we define what is meant by a polynomial-time nondeterministic algorithm. Definition A ***polynomial-time nondeterministic algorithm*** is a nondeterministic algorithm whose verification stage is a polynomial-time algorithm. Now we can define the set *NP.* Definition *NP* is the set of all decision problems that can be solved by polynomial-time nondeterministic algorithms. Note that *NP* stands for "nondeterministic polynomial." For a decision problem to be in *NP*, there must be an algorithm that does the verification in polynomial time. Because this is the case for the Traveling Salesperson Decision problem, that problem is in *NP.* It must he stressed that this does not mean that we necessarily have a polynomial-time algorithm that solves the problem. Indeed, we do not presently have one for the Traveling Salesperson Decision problem. If the answer for a particular instance of that problem were "yes," we might try all tours in the nondeterministic stage before trying one for which *verify* returns "true." If there were an edge from every vertex to every other vertex, there would be (*n* – 1)! tours. Therefore, if all tours were tried, the answer would not be found in polynomial time. Furthermore, if the answer for an instance were "no," solving the problem using this technique would absolutely require that all tours be tried. The purpose of introducing the concepts of non-deterministic algorithms and *NP* is to classify algorithms. There are usuallybetter algorithms for actually solving a problem than an algorithm that generates amid verifies strings. For example, the branch-and-bound algorithm for the Traveling Salesperson problem ([Algorithm 6.3](LiB0049.html#603)) does generate tours, but it avoids generating many of the tours by using a bounding function. Therefore, it is much better than an algorithm that blindly generates tours. What other decision problems are in *NP*? In the exercises you are asked to establish that the other decision problems in [Examples 9.2](#ch09ex02) to [9.5](#ch09ex05) are all in *NP*. Furthermore, there are thousands of other problems that no one has been able to solve with polynomial-time algorithms but that have been proven to be in *NP* because polynomial-time nondeterministic algorithms have been developed for them. (Many of these problems appear in Garey and Johnson, 1979.) Finally, there is a large number of problems that are trivially in *NP.* That is, *every problem in P is also in NP.* This is trivially true because any problem in *P* can be solved by a polynomial-time algorithm. Therefore, we can merely generate any nonsense in the nondeterministic stage and run that polynomial-time algorithm in the deterministic stage. Because the algorithm solves the problem by answering "yes" or "no," it verifies that, the answer is "yes" (for an instance where it is "yes") given any input string *S*. What decision problems are not in *NP*? Curiously, the only decision problems that have been proven not to be in *NP* are the same ones that have been proven to be intractable. That is, the Halting problem, Presburger Arithmetic, and the other problems discussed in [Section 9.3.2](LiB0076.html#894) have been proven not to be in *NP*. Again, we have found relatively few such problems. [Figure 9.3](#ch09fig03) shows the set of all decision problems. Notice that in this figure *NP* contains *P* as a proper subset. However, this may not be the case. That is, *no one has ever proven that there is a problem in NP that is not in P.* Therefore, *NP* – *P* may be empty. Indeed, the question of whether *P* equals *NP* is one of the most intriguing and important questions in computer science. This question is important, because, as we have already mentioned, most decision problems we have developed are in *NP.* Therefore, if *P* = *NP*, we would have polynomialtime algorithms for most known decision problems. [](fig9-3_0.jpg) Figure 9.3: The set of all decision problems. To show that *P* ≠ *NP* we would have to find a problem in *NP* that is not in *P*, whereas to show that *P* = *NP* we would have to find a polynomial-time algorithm for each problem in *NP.* Next we see that this latter task can be greatly simplified. That is, we show that it is necessary to find a polynomialtime algorithm for only one of a large class of problems. In spite of this great simplification, many researchers doubt that *P* equals *NP.* ### 9.4.2 NP-Complete Problems The problems in [Examples 9.2](#ch09ex02) to [Examples 9.5](#ch09ex05) may not all appear to have the same difficulty. For example, our dynamic programming algorithm ([Algorithm 3.11](LiB0030.html#340)) for the Traveling Salesperson problem is worst-case Θ (*n*22n). On the other hand, our dynamic programming algorithm (in [Section 4.4](LiB0036.html#427)) for the 0–1 Knapsack problem is worst-case Θ (2n). Furthermore, the state space tree in the branch-and-bound algorithm (Algorithm 6.3) for the Traveling Salesperson problemhas (*n* – 1)! leaves, whereas the one in the branch-and-bound algorithm (Algorithm 6.2) for the 0–1 Knapsack problem has only about 2*n*+1 nodes. Finally, our dynamic programming algorithm for the 0–1 Knapsack problem is Θ (*nW*), which means that it is efficient as long as the capacity *W* of the sack is not extremely large. In light of all this, it seems that perhaps the 0–1 Knapsack problem is inherently easier than the Traveling Salesperson problem. We show that in spite of this, these two problems, the other problems in [Examples 9.2](#ch09ex02) to [Examples 9.5](#ch09ex05), and thousands of other problems are all equivalent in the sense that if any one is in *P*, they all must be in *P.* Such problems are called ***NP-complete.*** To develop this result, we first describe a problem that is fundamental to the theory of *NP*-completeness–the problem of CNF-Satisfiability. Example 9.6 CNF–Satisfiability Problem****A ***logical (Boolean) variable*** is a variable that can have one of two values: true or false. If *x* is a logical variable,  is the negation of *x.* That is, *x* is true if and only if  is false. A **literal** is a logical variable or the negation of a logical variable. A ***clause*** is a sequence of literals separated by the logical **or** operator (∨). A logical expression in ***conjunctive normal form (CNF)*** is a sequence of clauses separated by the logical **and** operator (∧). The following is an example of a logical expression in CNF:  The ***CNF-Satisfiability Decision problem*** is to determine, for a given logical expression in CNF, whether there is some truth assignment (some set of assignments of true and false to the variables) that makes the expression true. **** Example 9.7****For the instance  the answer to CNF-Satisfiability is "yes," because the assignments *x*1 = true, *x*2 = false, and *x*3 = false make the expression true. For the instance  the answer to CNF-Satisfiability is "no," because no assignment of truth values makes the expression true. **** It is easy to write a polynomial-time algorithm that takes as input a logical expression in CNF and a set of truth assignments to the variables and verifies whether the expression is true for that assignment. Therefore, the problem is in *NP.* No one has ever found a polynomial-time algorithm for this problem, and no one has ever proven that it cannot be solved in polynomial time. So we do not know if it is in *P.* The remarkable thing about this problem is that in 1971, Stephen Cook published a paper proving that if CNF-Satisfiability is in *P*, then *P* = *NP.* (A variation of this theorem was published independently by L. A. Levin in 1973.) Before we can state the theorem rigorously, we need to develop a new concept—namely, the concept of *polynomial-time reducibility.* Suppose we want to solve decision problem *A* and we have an algorithm that solves decision problem *B.* Suppose further that we can write an algorithm that creates an instance *y* of problem *B* from every instance *x* of problem *A* such that an algorithm for problem *B* answers "yes" for *y* if and only if the answer to problem *A* is "yes" for *x.* Such an algorithm is called a *transformation algorithm* and is actually a function that maps every instance of problem *A* to an instance of problem *B.* We can denote it as follows:  The transformation algorithm combined with an algorithm for problem *B* yields an algorithm for problem *A.* [Figure 9.4](#ch09fig04) illustrates this. [](fig9-4_0.jpg) Figure 9.4: Algorithm *tran* is a transformation algorithm that maps each instance *x* of decision problem *A* to an instance *y* of decision problem *B.* Together with the algorithm for decision problem *B*, it yields an algorithm for decision problem *A.* The following example has nothing to do with the theory of NP-completeness. We present it because it is a simple example of a transformation algorithm. Example 9.8 A Transformation Algorithm****Let our first decision problem be: Given *n* logical variables, does at least one of them have the value "true"? Let our second decision problem be: Given *n* integers, is the largest of them positive? Let our transformation be: ****  where *k*1 is 1 if *x*1 is true and *k**i* is 0 if *x**i* is false. An algorithm for our second problem returns "yes" if and only if at least one *k**i* is 1, which is the case if and only if at least one *x**i* is true. Therefore, an algorithm for the second problem returns "yes" if and only if at least one *x**i* is true, which means that our transformation is successful, and we can solve the first problem using an algorithm for the second problem. We have the following definition pertaining to the concepts just developed. Definition If there exists a polynomial-time transformation algorithm from decision problem *A* to decision problem *B*, problem *A* is ***polynomialtime many-one reducible*** to problem *B.* (Usually we just say that problem *A* reduces to problem *B.*) In symbols, we write  We say "many-one" because a transformation algorithm is a function that may map many instances of problem *A* to one instance of problem *B.* That is, it is a many-one function. If the transformation algorithm is polynomial-time and we have a polynomialtime algorithm for problem *B*, intuitively it seems that the algorithm for problem *A* that results from combining the transformation algorithm and the algorithm for problem *B* must be a polynomial-time algorithm. For example, it is clear that the transformation algorithm in [Example 9.8](#ch09ex08) is polynomial-time. Therefore, it seems that if we run that algorithm followed by some polynomialtime algorithm for the second problem, we are solving the first problem in polynomial time. The following theorem proves that this is so. Theorem 9.1****If decision problem *B* is in *P* and  then decision problem *A* is in *P.* Proof: Let *p* be a polynomial that bounds the time complexity of the polynomialtime transformation algorithm from problem *A* to problem *B*, and let *q* be a polynomial that bounds the time complexity of a polynomial-time algorithm for *B*. Suppose we have an instance of problem *A* that is of size *n*. Because at most there are *p* (*n*) steps in the transformation algorithm, and at worst that algorithm outputs a symbol at each step, the size of the instance of problem *B* produced by the transformation algorithm is at most *p* (*n*). When that instance is the input to the algorithm for problem *B*, this means that there are at most *q* \[*p* (*n*)\] steps. Therefore, the total amount of work required to transform the instance of problem *A* to an instance of problem *B* and then solve problem *B* to get the correct answer for problem *A* is at most  which is a polynomial in *n*. **** Next we define *NP*-complete. Definition A problem B is called *NP*-complete if both of the following are true: 1. B is in *NP*. 2. For every other problem A in *NP*  By [Theorem 9.1](#ch09ex09), *if we could show that any NP-complete problem is in P, we could conclude that P = NP.* In 1971 Stephen Cook managed to find a problem that is *NP*-complete. The following theorem states his result. Theorem 9.2****(Cook's Theorem) CNF-Satisfiability is *NP*-complete. Proof: The proof can be found in Cook (1971) and in Garey and Johnson (1979). **** Although we do not prove Cook's theorem here, we mention that the proof does not consist of reducing every problem! in *NP* individually to CNF-Satisfiability. If this were the case, whenever a new problem in *NP* was discovered, it would be necessary to add its reduction to the proof. Rather, the proof exploits common properties of problems in *NP* to show that any problem in this set must reduce to CNF-Satisfiability. Once this ground-breaking theorem was proven, many other problems were proven to he NP-complete. These proofs rely on the following theorem. Theorem 9.3****A problem *C* is *NP*-complete if both of the following are true: 1. C is in *NP.* 2. For some other *NP*-complete problem *B*,  Proof: Because *B* is *NP*-complete, for any problem *A* in *NP*, *A* α *B.* It is not hard to see that reducibility is transitive. Therefore, *A* α *C.* Because *C* is in *NP*, we can conclude that *C* is *NP*-complete. **** By Cook's theorem and [Theorem 9.3](#ch09ex11), we can show that a problem is *NP*-complete by showing that it is in *NP* and that CNF-Satisfiability reduces to it. These reductions are typically much more complex than the one given in [Example 9.7](#ch09ex07). We give one such reduction next. Example 9.9****We show that the Clique Decision problem is *NP*-complete. It is left as an exercise to show it is in *NP* by writing a polynomial-time verification algorithm for this problem. Therefore, we need only show that  to conclude that the problem is *NP*-complete. First recall that a *clique* in an undirected graph is a subset of vertices such that each vertex in the subset is adjacent to all the other vertices in the subset, and that the Clique Decision problem is to determine for a graph and a positive integer k whether the graph has a clique containing at least *k* vertices. Let  be a logical expression in CNF, where each *C**i* is a clause of *B*, and let *x*1, *x*2, …, *x**n* be the variables in *B.* Transform *B* to a graph *G* = (*V, E*), as follows:  A sample construction of *G* is shown in [Figure 9.5](#ch09fig05). It is left as an exercise to show that this transformation is polynomial-time. Therefore, we need only show that *B* is CNF-Satisfiable if and: only if *G* has a clique of size at least *k.* We do this next. 1. Show that if *B* is CNF-Satisfiable, *G* has a clique of size at least *k*: If *B* is CNF-Satisfiable, there are truth assignments for *x*1, *x*2, …, *x**n* such that each clause is true with these assignments. This means that with theseassignments there is at least one literal in each *C**i* that is true. Pick one such literal from each *C**i*. Then let  Clearly, *V*’ forms a clique in *G* of size *k.* 2. Show that if *C* has a clique of size at least *k*, *B* is CNF-Satisfiable: Because there cannot be an edge from a vertex (*y*, *i*) to a vertex (*z*, *i*), the indices in the vertices in a clique must all be different. Because there are only *k* different indices, this means that a clique can have at most *k* vertices. So if *G* has a clique (*V*’, *E*’) of size at least *k*, the number of vertices in V’ must be exactly k. Therefore, if we set  *S* contains k literals. Furthermore, *S* contains a literal from each of the *k* clauses, because there is no edge connecting (*y*, *i*) and (*z*, *i*) for any literals *y* and *z* and index *i.* Finally, *S* cannot contain both a literal *y* and its complement , because there is no edge connecting (*y*, *i*) and (, *j*) for any *i* and *j.* Therefore, if we set  and assign arbitrary truth values to variables not in *S*, all clauses in *B* are true. Therefore, *B* is CNF-Satisfiable. **** [](fig9-5_0.jpg) Figure 9.5: The graph *G* in [Example 9.9](#ch09ex12) when *B* = . Recall the Hamiltonian Circuits problem from [Section 5.6](LiB0044.html#530). The ***Hamiltonian Circuits Decision problem*** is to determine whether a connected, undirected graph has at least one tour (a path that starts at one vertex, visits each vertex in the graph once, and ends up at the starting vertex). It is possible to show that  The reduction is even more tedious than the one given in the previous example and can be found in Horowitz and Sahni (1978). It is left an exercise to write a polynomial-time verification algorithm for this problem. Therefore, we can conclude that the Hamiltonian Circuits Decision problem is *NP*-complete. Now that we know that the Clique Decision problem and the Hamiltonian Circuits Decision problem are *NP* -complete, we can show that some other problem in *NP* is *NP*-complete by showing that the Clique Decision problem or the Hamiltonian Circuits Decision problem reduces to that problem (by [Theorem 9.3](#ch09ex11)). That is, we do not need to return to CNF-Satisfiability for each proof of *NP*-completeness. More sample reductions follow. Example 9.10****Consider a variant of the Traveling Salesperson Decision problem in which the graph is undirected. That is, given a weighted, undirected graph and a positive number *d*, determine whether there is an undirected tour having total weight no greater than *d.* Clearly, the polynomial-time verification algorithm given earlier for the usual Traveling Salesperson problem also works for this problem. Therefore the problem is in *NP*, and we need only show that some *NP*-complete problem reduces to it to conclude that it is *NP*-complete. We show that  Transform an instance (*V*, *E*) of the Hamiltonian Circuits Decision problem to the instance (*V*, *E*’) of the Traveling Salesperson (Undirected) Decision problem that has the same set of vertices *V*, has an edge between every pair of vertices, and has the following weights:  An example of this transformation is shown in [Figure 9.6](#ch09fig06). Clearly, (*V*, *B*) has a Hamiltonian Circuit if and only if (*V*, *E*’) has a tour with total weight no more than n, where n is the number of vertices in *V.* It is left as an exercise to complete this example by showing that the transformation is polynomial-time. **** [](fig9-6_0.jpg) Figure 9.6: The transformation algorithm in [Example 9.10](#ch09ex13) maps the undirected graph on the left to the weighted, undirected graph on the right. Example 9.11****We have already written a polynomial-time verification algorithm for the usual 71 Traveling Salesperson Decision problem. Therefore, this problem is in *NP*, and we can show that it is *NP*-complete by showing that ****  Transform an instance (*V*, *E*) of the Traveling Salesperson (Undirected) Decision problem to the instance (*V*, *E*’) of the Traveling Salesperson problem that has the same set of vertices *V* and has the edges (*u*, *v*) and (*v*, *u*) both in *E*’ whenever (*u*, *v*) is in *E*. The directed weights of (*u*, *v*) and (*v*, *u*) are the same as the undirected weight of (*u*, *v*). Clearly, (*V*, *E*) has an undirected tour with total weight no greater than *d* if and only if (*V*, *E*’) has a directed tour with total weight no greater than *d*. It is left as an exercise to complete this example by showing that the transformation is polynomial-time. As mentioned previously, thousands of problems, including the other problems in [Examples 9.2](#ch09ex02) to [Examples 9.5](#ch09ex05), have been shown to be *NP*-complete using reductions like those just given. Garey and Johnson (1979) contains many sample reductions and lists over 300 *NP*-complete problems. ### The State of NP [Figure 9.3](#ch09fig03) shows *P* as a proper subset of *NP*, but, as mentioned previously, they may be the same set. How does the set of *NP*-complete problems fit into the picture? First, by definition, it is a subset of *NP.* Therefore, Presburger Arithmetic, the Halting problem, and any other decision problems that are not in *NP* are not *NP*-complete. A decision problem that is in *NP* and is not *NP*-complete is the trivial decision problem that answers "yes" for all instances (or answers "no" for all instances). This problem is not *NP*-complete because it is not possible to transform a nontrivial decision problem to it. If *P* = *NP*, the situation is as depicted on the left in [Figure 9.7](#ch09fig07). If *P* ≠ *NP*, the situation is as depicted on the right in that figure. That is, if *P* & *NP*, then  where ***NP-complete*** denotes the set of all *NP*-complete problems. This is so because if some problem in *P* were *NP*-complete, [Theorem 9.1](#ch09ex09) would imply that we could solve any problem in *NP* in polynomial time. [](fig9-7_0.jpg) Figure 9.7: The set *NP* is either as depicted on the left or as depicted on the right. Notice that [Figure 9.7](#ch09fig07) (on the right) says that the Graph Isomorphism problem may be in  This problem concerns graph isomorphism, which is defined as follows. Two graphs (undirected or directed) *G* = (*V*, *B*) and *G*’ = (*V*’, *E*)’ are called ***isomorphic*** if there is a one-to-one function *f* from *V* onto *V*’ such that for every *v*1 and *v*2 in *V*, the edge (*u*, *v*) is in *E* if and only if the edge (*f* (*u*), *f* (*v*)) is in *E*’. The Graph Isomorphism problem is as follows: Example 9.12 Graph Isomorphism Problem*****Given two graphs G = (V, E) arid G’ = (V’, B’), are they isomorphic?* **** The directed graphs in [Figure 9.8](#ch09fig08) are isomorphic owing to the function  [](fig9-8_0.jpg) Figure 9.8: These graphsare isomorphic. It is left as an exercise to write a polynomial-time verification algorithm for the Graph Isomorphism problem, and thereby show it is in *NP.* A straightforward algorithm for this problem is to check all *n*! one-to-one onto mappings, where *n* is the number of vertices. This algorithm has worse than exponential time complexity. No one has ever found a polynomial-time algorithm for this problem; yet no one has ever proven it is *NP*-complete. Therefore, we do not know whether it is in *P* and we do not know whether it is *NP*-complete. No one has been able to prove that there is a problem in *NP* that is neither in *P* nor *NP*-complete (such a proof would automatically prove that *P* $ *NP*). However, it has been proved that, if *P* ≠ *NP*, such a problem must exist. This result, which is stated on the right in [Figure 9.7](#ch09fig07), is formalized in the following theorem. Theorem 9.4****If *P* ≠ *NP*, the set  is not empty. **Proof**: The proof follows from a more general result that can be found in Ladner (1975) **** ### Complementary Problems Notice the similarity between the following two problems. Example 9.13 Primes Problem****Given a positive integer *n*, is *n* a prime number? **** Example 9.14 Composite Numbers Problem****Given a positive integer *n*, are there integers *m* > 1 and *k* > 1 such that *n* = *mk*? **** The Primes problem is the one solved by the algorithm at the beginning of [Section 9.2](LiB0075.html#887). It is the complementary problem to the Composite Numbers problem. In general, the ***complementary problem*** to a decision problem is the problem that answers "yes" whenever the original problem answers "no" and answers "no" whenever the original problem answers "yes." Another example of a complementary problem follows. Example 9.15 Complementary Traveling Salesperson Decision Problem****Given a weighted graph, and a positive number *d*, is there no tour with total weight no greater than *d*? **** Clearly, if we found an ordinary deterministic polynomial-time algorithm for a problem, we would have a deterministic polynomial-time algorithm for its complementary problem. For example, if we could determine in polynomialtime whether a number was composite, we would also be determining whether it was prime. However, finding a polynomial-time nondeterministic algorithm for a problem does not automatically produce a polynomial-time nondeterministic algorithm for its complementary. That is, showing that one is in *NP* does not automatically show that the other is in *NP.* In the case of the Complementary Traveling Salesperson problem, the algorithm would have to be able to verify in polynomial time that no tour with weight no greater than *d* exists. This is substantially more complex than verifying that a tour has weight no greater than *d.* No one has ever fund a polynomial-time verification algorithm for the Complementary Traveling Salesperson Decision Problem. Indeed, no one has ever shown that the complementary problem to any known *NP*-complete problems is in *NP.* On the other hand, no one has ever proven that some problem is in *NP* whereas its complementary problem is not in *NP.* The following result has been obtained. Theorem 9.5****If the complementary problem to any *NP*-complete problem is in *NP*, the complementary problem to every problem in *NP* is in *NP.* Proof: The proof can be found in Garey and Johnson (1979). **** Let's discuss the Graph Isomorphism and Primes problem further. As mentioned in the previous subsection, no one has ever found a polynomial-time algorithm for the Graph Isomorphism problem, yet no one has proven that it is *NP*-complete. Until recently, the same was true of the Primes problem. However, in 2002 Agrawal et al. developed a polynomial-time algorithm for the Primes problem. We present that algorithm in Section 10.6. Before than, in 1975 Pratt had shown the Primes problem to be in *NP*, and its is straightforward to show its complementary problem (the Composite Numbers problem) is in *NP.* Similarly, the Linear Programming problem and its complementary problem were both shown to be in *NP* before Chachian (1979) developed a polynomial-time algorithm for it. On the other hand, no one has been able to show the complementary problem to the Graph Isomorphism problem is in *NP.* Given these results, it seems more likely that the Graph Isomorphism problem will be shown to be *NP*-complete than that we will find a polynomial-time algorithm for it. On the other hand, it may be in the set *NP* – (*P* U *NP*-complete). ### 9.4.3 NP-Hard, NP-Easy, and NP-Equivalent Problems So far we have discussed only decision problems. Next we extend our results to problems in general. Recall that [Theorem 9.1](#ch09ex09) implies that if decision problem *A* is polynomial-time many-one reducible to problem *B*, then we could solve problem *A* in polynomial time using a polynomial-time algorithm for problem *B.* We generalize this notion to nondecision problems with the following definition. Definition If problem *A* can be solved in polynomial time using a hypothetical polynomial time algorithm for problem *B*, then problem *A* is ***polynomial-time Turing reducible*** to problem *B.* (Usually we just say *A* Turing reduces to *B.*) In symbols, we write  This definition does not require that a polynomial-time algorithm for problem *B* exist. It only says that *if* one did exist, problem A would also be solvable in polynomial time. Clearly, if *A* and *B* are both decision problems, then  Next we extend the notion of *NP*-completeness to nondecision problems. Definition A Problem *B* is called ***NP-hard*** if, for some *NP*-complete problem *A*,  It is not hard to see that Turing reductions are transitive. Therefore, all problems in *NP* reduce to any *NP*-hard problem. This means that *if a polynomialtime algorithm exists for any NP-hard problem, then P = NP.* What problems are *NP*-hard? Clearly, *every NP-complete problem is NP-hard.* Therefore, we ask instead what nondecision problems are *NP*-hard. Earlier we noted that if we could find a polynomial-time algorithm for an optimization problem, we would automatically have a polynomial-time algorithm for the corresponding decision problem. Therefore, *the optimization problem corresponding to any NP-complete problem is N-hard.* The following example formally uses the definition of Turing reducibility to show this result for the Traveling Salesperson problem. Example 9.16 The Traveling Salesperson Optimization Problem Is *NP*–hard****Suppose we had a hypothetical polynomial-time algorithm for the Traveling Salesperson Optimization problem. Let the instance of the Traveling Salesperson Decision problem containing the graph *G* and positive integer *d* be given.Apply the hypothetical algorithm to the graph *G* to obtain the optimal solution *mindist.* Then our answer for the instance of the decision problem would be "no" if *d* $ *mindist* and "yes" otherwise. Clearly, the hypothetical polynomialtime algorithm for the optimization problem, along with this extra step, gives the answer to the decision problem in polynomial time. Therefore, Traveling Salesperson Decision problem > αT Traveling Salesperson Optimization problem. **** What problems are not *NP*-hard? We do not know if there is any such problem. Indeed, *if we were to prove that some problem was not NP-hard, we would be proving that P ≠ NP.* The reason is that if *P* = *NP*, then each problem in *NP* would be solvable by a polynomial-time algorithm. Therefore, we could solve each problem in *NP*, using a hypothetical polynomial-time algorithm for any problem *B*, by simply calling the polynomial-time algorithm for each problem. We don't even need the hypothetical algorithm for problem *B.* Therefore, all problems would be *NP*-hard. On the other hand, any problem for which we have found a polynomialtime algorithm may not be *NP*-hard. Indeed, *if we were to prove that some problem for which we had a polynomial-time algorithm was NP-hard, we would be proving that P = NP.* The reason is that we would then have an actual rather than a hypothetical polynomial-time algorithm for some *NP*-hard problem. Therefore, we could solve each problem in *NP* in polynomial-time using the Turing reduction from the problem to the *NP*-hard problem. [Figure 9.9](#ch09fig09) illustrates how the set of *NP*-hard problems fits into the set of all problems. [](fig9-9_0.jpg) Figure 9.9: The set of all problems If a problem is *NP*-hard, it is at least as hard (in terms of our hopes of finding a polynomial-time algorithm) as the *NP*-complete problems. For example, the Traveling Sales Optimization problem is at. least as hard as the *NP*-complete problems. However, is the reverse necessarily true? That is, are the *NP*-complete problems at least as hard as the Traveling Salesperson Optimization problem? *NP*-hardness does not imply this. We need another definition. Definition A problem A is called ***NP-easy*** if, for some problem *B* in *NP*,  *Clearly, if P = NP, then a polynomial-time algorithm exists for all NP-easy problems.* Notice that our definition of *NP*-easy is not exactly symmetrical with our definition of *NP*-hard. It is left as an exercise to show that a problem is *NP*-easy if and only if it reduces to an *NP*-complete problem. What problems are *NP*-easy? Obviously, the problems in *P*, the problems in *NP*, and nondecision problems for which we have found polynomial-time algorithms are all *NP*-easy. The optimization problem, corresponding to an *NP*-complete decision problem, can usually be shown to be *NP*-easy. However, it is not trivial to do this, as the following example illustrates. Example 9.17****The Traveling Salesperson Optimization problem is *NP*-easy. To establish this result, we introduce the following problem. **** ### Traveling Salesperson Extension Decision Problem Let an instance of the Traveling Salesperson Decision problem be given, where the number of vertices in the graph is *n* and the integer is *d.* Furthermore, let a partial tour *T* consisting of *m* distinct vertices be given. The problem is to determine whether *T* can be extended to a complete tour having total weight no greater than *d*. The parameters for this problem are the same as those for the Traveling Salesperson Decision problem plus the partial tour *T.* It is not hard to show that the Traveling Salesperson Extension Decision problem is in *NP.* Therefore, in order to obtain our desired result, we need only show that  To that end, let *polyalg* be a hypothetical polynomial-time algorithm for Traveling Salesperson Extension Decision problem. The inputs to *polyalg* a graph, a partial tour, and a distance. Let an instance *G* of size *n* of Traveling Salesperson Optimization problem be given. Let the vertices in instance be  and set  If *mindist* is the total weight of the edges in an optimal tour, then  Because any vertex can be the first vertex on our tour, we can make *v*1 the first vertex. Consider the following call:  The partial tour that is the input to this call is simply \[*v*1\], which is the partial tour before we ever leave *v*1. The smallest value of *d* for which this call could return "true" is *d* = *dmin*, and if there is a tour, the call will definitely return "true" if *d* = *dmax.* If it returns "false" for *d* = *dmax*, then *mindist* = ∞. Otherwise, using a binary search, we can determine the smallest value of *d* for which polyalg returns "true" when *G* and \[*v*1\] are the inputs. That value is *mindist.* This means that we can compute mindist in at most about lg(*dmax*) calls to *polyalg*, which means that we can compute mindist in polynomial time. Once we know the value of *mindist*, we.use *polyalg* to construct an optimal tour in polynomial time, as follows. If *mindist* = ∞, there are no tours, and we are done. Otherwise, say that a partial tour is ***extendible*** if it can be extended to a tour having total weight equal to *mindist.* Clearly, \[*v*1\] is extendible. Because \[*v*1\] is extendible, there must be at least one *v**i* such that \[*v*1, *v**i*\] is extendible. We can determine such a *v**i* by calling *polyalg* at most *n* – 2 times, as follows:  where 2 ≤ *i* ≤ *n* – 1. We stop when we find an extendible tour or when *i* reaches *n* – 1. We need not check the last vertex, because, if the others all fail, the last vertex must be extendible. In general, given an extendible partial tour containing *m* vertices, we can find an extendible partial tour containing *m* + 1 vertices with at most *n* – *m* – 1 calls to *polyalg.* So we can build an optimal tour with at most the following number of calls to *polyalg:*  This means that we can also construct an optimal tour in polynomial time, and we have a polynomial-time Turing reduction. Similar proofs have been established for the other problems in [Examples 9.2](#ch09ex02) to [Examples 9.5](#ch09ex05). and for the optimization problems corresponding to most *NP*-complete decision problems. We have the following definition concerning such problems. Definition A problem is called ***NP-equivalent*** if it is both *NP*-hard and *NP*-easy. Clearly, *P = NP if and only if polynomial-time algorithms exist for all NP-equivalent problems.* We see that originally restricting our theory to decision problems causes no substantial loss in generality, because we can usually show that the optimization problem, corresponding to an *NP*-complete decision problem, is *NP*-equivalent. This means that finding a polynomial-time algorithm for the optimization problem is equivalent to finding one for the decision problem. Our goal has been to provide a facile introduction to the theory of *NP.* For a more thorough introduction, you are referred to the text we have referenced several times—namely, Garey and Johnson (1979). Although that text is quite old, it is still one of the best comprehensive introductions to the *NP* theory. Another good introductory text is Papadimitriou (1994).