# Chapter 9: Computational Complexity and Interactability鈥擜n Introduction to the Theory of NP Consider the following scenario based on a story in Garey and Johnson (1979). Suppose you work in industry, and your boss gives you the task of finding an efficient algorithm for some problem very important to the company. After laboring long hours on the problem for over a month, you make no headway at all toward an efficient algorithm. Giving up, you return to your boss and ashamedly announce that you simply can't find an efficient algorithm. Your boss threatens to fire you and replace you with a smarter algorithm designer. You reply that perhaps it is not that you're stupid, but rather that an efficient algorithm is not possible. Reluctantly, your boss gives you another month to prove that this is the case. After a second month of burning the midnight oil trying to prove this, you are unsuccessful. At this point you've failed to obtain an efficient algorithm and you've failed to prove that such an algorithm is not possible. You are on the verge of being fired, when you recall that some of the greatest computer scientists have worked on creating an efficient algorithm for the Traveling Salesperson problem, but nobody has ever developed one whose worst-case time complexity is better than exponential. Furthermore, no one has ever proven that such an algorithm is not possible. You see one last glimmer of hope. If you could prove that an efficient algorithm for the company's problem would automatically yield an efficient algorithm for the Traveling Salesperson problem, it would mean that your boss is asking you to accomplish something that has eluded some of the greatest computer scientists. You ask for a chance to prove this, and your boss reluctantly agrees. After only a week of effort, you do indeed prove that an efficient algorithm for the company's problem would automatically yield an efficient algorithm for the Traveling Salesperson problem. Rather than being fired, you're given a promotion because you have saved the company a lot of money. Your boss now realizes that it would not be prudent to continue to expend great effort looking for an exact algorithm for the company's problem and that other avenues, such as looking for an approximate solution, should be explored. What we have just described is exactly what computer scientists have successfully done for the last 25 years. We have shown that the Traveling Salesperson problem and thousands of other problems are equally hard in the sense that if we had an efficient algorithm for any one of them, we would have efficient algorithms for all of them. Such an algorithm has never been found, but it's never been proven that one is not possible. These interesting problems are called ***NP-complete*** and are the focus of this chapter. A problem for which an efficient algorithm is not possible is said to be "intractable." In [Section 9.1](LiB0079.html#985) we explain more concretely what it means for a problem to be intractable. [Section 9.2](LiB0075.html#887) shows that when we are concerned with determining whether or not a problem is intractable, we must be careful about what we call the input size in an algorithm. [Section 9.3](LiB0076.html#892) discusses three general categories in which problems can be grouped as far as intractability is concerned. The culmination of this chapter, [Section 9.4](LiB0077.html#898), discusses the theory of *NP* and *NP-complete* problems. [Section 9.5](LiB0078.html#957) shows ways of handling NP-complete problems. ## 9.1 Interactability The dictionary defines *intractable* as "difficult to treat or work." This means that a problem in computer science is intractable if a computer has difficulty solving it. This definition is too vague to be of much use to us. To make the notion more concrete, we now introduce the concept of a "polynomial-time algorithm." Definition聽A ***polynomial-time algorithm*** is one whose worst-case time complexity is bounded above by a polynomial function of its input size. That is, if *n* is the input size, there exists a polynomial *p* (*n*) such that  Example 9.1****Algorithms with the following worst-case time complexities are all polynomialtime.  Algorithms with the following worst-case time complexities are not polynomialtime.  **** Notice that *n* lg *n* it is not a polynomial in *n.* However, because  it is bounded by a polynomial in n, which means that an algorithm with this time complexity satisfies the criterion to be called a polynomial-time algorithm. In computer science, a problem is called ***intractable*** if it is impossible to solve it with a polynomial-time algorithm. We stress that intractability is a property of a problem; it is not a property of any one algorithm for that problem. For a problem to be intractable, there must be no polynomial-time algorithm that solves it. Obtaining a nonpolynomial-time algorithm for a problem does not make it intractable. For example, the brute-force algorithm for the Chained Matrix Multiplication problem (see [Section 3.4](LiB0028.html#290)) is nonpolynomialtime. So is the divide-and-conquer algorithm that uses the recursive property established in [Section 3.4](LiB0028.html#290). However, the dynamic programming algorithm (Algorithm 3.6) developed in that section is 螛 (*n*3). The problem is not intractable, because we can solve it in polynomial time using Algorithm 3.5. In [Chapter 1](LiB0008.html#16) we saw that polynomial-time algorithms are usually much better than algorithms that are not polynomial-time. Looking again at [Table 1.4](LiB0011.html#82), we see that if it takes 1 nanosecond to process the basic instructions, an algorithm with a time complexity of *n*3 will process an instance of size 100 in 1 millisecond, whereas an algorithm with a time complexity of 2*n* will take billions of years. We can create extreme examples in which a nonpolynomial-time algorithm is better than a polynomial-time algorithm for practical input sizes. For example, if n = 1,000,000,  Furthermore, many algorithms whose worst-case time complexities are not polynomials have efficient running times for many actual instances. This is the case for many backtracking and branch-and-bound algorithms. Therefore, our definition of intractable is only a good indication of real intractability. In any particular case, a problem for which we have found a polynomial-time algorithm could possibly be more difficult to handle, as far as practical input sizes are concerned, than one for which we cannot find such an algorithm. There are three general categories of problems as far as intractability is concerned: 1. Problems for which polynomial-time algorithms have been found 2. Problems that have been proven to be intractable 3. Problems that have not been proven to be intractable, but for which polynomial-time algorithms have never been found It is a surprising phenomenon that most problems in computer science seem to fall into either the first or third category. When we are determining whether an algorithm is polynomial-time, it is necessary to be careful about what we call the input size. Therefore, before proceeding, let's discuss the input size further. (See [Section 1.3](LiB0010.html#57) for our initial discussion of the input size.)