UC Berkeley—CS 170: Efficient Algorithms and Intractable Problems Handout 19Lecturer: Michael Jordan November 23, 2005Notes 19 for CS 1701 Tractable and Intractable ProblemsSo far, almost all of the problems that we have studied have had complexities that are poly-nomial, i.e., whose running time T (n) has been O(nk) for some fixed value of k. Typicallyk has been small, 3 or less. We will let P denote the class of all problems whose solutioncan be computed in polynomial time, i.e., O(nk) for some fixed k, whether it is 3, 100, orsomething else. We consider all such problems efficiently solvable, or tractable. Notice thatthis is a very relaxed definition of tractability, but our goal in this lecture and the nextfew ones is to understand which problems are intractable, a notion that we formalize as notbeing solvable in polynomial time. Notice how not being in P is certainly a strong way ofbeing intractable.We will focus on a class of problems, called the NP-complete problems, which is a class ofvery diverse problems, that share the following properties: we only know how to solve thoseproblems in time much larger than polynomial, namely exponential time, that is 2O(nk)forsome k; and if we could solve one NP-complete problem in polynomial time, then there isa way to solve every NP-complete problem in polynomial time.There are two reasons to study NP-complete problems. The practical one is that if yourecognize that your problem is NP-complete, then you have three choices:1. you can use a known algorithm for it, and accept that it will take a long time to solveif n is large;2. you can settle for approximating the solution, e.g., finding a nearly best solution ratherthan the optimum; or3. you can change your problem formulation so that it is in P rather than being NP-complete, for example by restricting to work only on a subset of simpler problems.Most of this material will concentrate on recognizing NP-complete problems (of whichthere are a large number, and which are often only slightly different from other, familiar,problems in P) and on some basic techniques that allow to solve some NP-complete problemsin an approximate way in polynomial time (whereas an exact solution seems to requireexponential time).The other reason to study NP-completeness is that one of the most famous open problemin computer science concerns it. We stated above that “we only know how to solve NP-complete problems in time much larger than polynomial” not that we have proven that NP-complete problems require exponential time. Indeed, this is the million dollar question,1one of the most famous open problems in computer science, the question whether “P =NP?”, or whether the class of NP-complete problems have polynomial time solutions. After1This is not a figure of speech. See http://www.claymath.org/prizeproblems.Notes number 19 2decades of research, everyone believes that P6=NP, i.e., that no polynomial-time solutionsfor these very hard problems exist. But no one has proven it. If you do, you will be veryfamous, and moderately wealthy.So far we have not actually defined what NP-complete problems are. This will take sometime to do carefully, but we can sketch it here. First we define the larger class of problemscalled NP: these are the problems where, if someone hands you a potential solution, thenyou can check whether it is a solution in polynomial time. For example, suppose the problemis to answer the question “Does a graph have a simple path of length |V |?”. If someonehands you a path, i.e., a sequence of vertices, and you can check whether this sequenceof vertices is indeed a path and that it contains all vertices in polynomial time, then theproblem is in NP. It should be intuitive that any problem in P is also in NP, because areall familiar with the fact that checking the validity of a solution is easier than coming upwith a solution. For example, it is easier to get jokes than to be a comedian, it is easier tohave average taste in books than to write a best-seller, it is easier to read a textbook in amath or theory course than to come up with the proofs of all the theorems by yourself. Forall this reasons (and more technical ones) people believe that P6=NP, although nobody hasany clue how to prove it. (But once it will be proved, it will probably not be too hard tounderstand the proof.)The NP-complete problems have the interesting property that if you can solve any oneof them in polynomial time, then you can solve every problem in NP in polynomial time.In other words, they are at least as hard as any other problem in NP; this is why they arecalled complete. Thus, if you could show that any one of the NP-complete problems thatwe will study cannot be solved in polynomial time, then you will have not only shown thatP6=NP, but also that none of the NP-compete problems can be solved in polynomial time.Conversely, if you find a polynomial-time algorithm for just one NP-complete problem, youwill have shown that P=NP.22 Decision ProblemsTo simplify the discussion, we will consider only problems with Yes-No answers, rather thanmore complicated answers. For example, consider the Traveling Salesman Problem (TSP)on a graph with nonnegative integer edge weights. There are two similar ways to state it:1. Given a weighted graph, what is the minimum length cycle that visits each nodeexactly once? (If no such cycle exists, the minimum length is defined to be ∞.)2. Given a weighted graph and an integer K, is there a cycle that visits each node exactlyonce, with weight at most K?Question 1 above seems more general than Question 2, because if you could answer Question1 and find the minimum length cycle, you could just compare its length to K to answerQuestion 2. But Question 2 has a Yes/No answer, and so will be easier for us to consider. In2Which still entitles you to the million dollars, although the sweeping ability to break every cryptographicprotocol and to hold the world banking and trading systems by ransom might end up being even moreprofitable.Notes number 19 3Reduction R Algorithm for BAlgorithm for A‘‘yes’’‘‘no’’input of Ax R(x)(inputof B)Figure 1: A reduction.particular, if we show that Question 2 is NP-complete (it is), then that means that Question1 is at least as hard, which will be good enough for us.3Another example of a problem with a Yes-No answer is circuit satisfiability (which weabbreviate CSAT). Suppose we are given a Boolean circuit with n Boolean inputs x1, ...,