Tracable and Non Tracable problems
Tractable and Intractable Problems
So far, almost all of the problems that we have studied have had complexities that are
polynomial, i.e. whose running time T(n) has been O(n^k) for some fixed value of k. Typically k has been small, 3 or less. We will let P denote the class of all problems whose solution can be computed in polynomial time, i.e. O(n^k) or some fixed k, whether it is 3, 100, or something else. We consider all such problems efficiently solvable, or tractable. Notice that this is a very relaxed definition of tractability, but our goal in this lecture and the next few ones is to understand which problems are intractable, a notion that we formalize as not being solvable in polynomial time. Notice how not being in P is certainly a strong way of being intractable.
We will focus on a class of problems, called the NP-complete problems, which is a class of very diverse problems, that share the following properties: we only know how to solve those problems in time much larger than polynomial, namely exponential time, that is 2 O(n^k) for some k; and if we could solve one NP-complete problem in polynomial time, then there is a 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 you
recognize 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 solve
if n is large;
2. you can settle for approximating the solution, e.g. finding a nearly best solution rather than the optimum; or
3. 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 which there 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 problems in an approximate way in polynomial time (whereas an exact solution seems to require exponential time).
The other reason to study NP-completeness is that one of the most famous open problem in 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,1
one 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. After decades of research, everyone believes that P is not equal to NP, i.e. that no polynomial-time solutions for these very hard problems exist. But no one has proven it. If you do, you will be very
famous, and moderately wealthy.
So far we have not actually defined what NP-complete problems are. This will take some time to do carefully, but we can sketch it here. First we define the larger class of problems called NP: these are the problems where, if someone hands you a potential solution, then you can check whether it is a solution in polynomial time. For example, suppose the problem is to answer the question “Does a graph have a simple path of length |V |?”. If someone
hands you a path, i.e. a sequence of vertices, and you can check whether this sequence of vertices is indeed a path and that it contains all vertices in polynomial time, then the problem is in NP. It should be intuitive that any problem in P is also in NP, because are all familiar with the fact that checking the validity of a solution is easier than coming up with a solution. For example, it is easier to get jokes than to be a comedian, it is easier to have average taste in books than to write a best-seller, it is easier to read a textbook in a math or theory course than to come up with the proofs of all the theorems by yourself. For
all this reasons (and more technical ones) people believe that P not =NP, although nobody has any clue how to prove it. (But once it will be proved, it will probably not be too hard to understand the proof.)
The NP-complete problems have the interesting property that if you can solve any one of 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 are called complete. Thus, if you could show that any one of the NP-complete problems that
we will study cannot be solved in polynomial time, then you will have not only shown that P not =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, you will have shown that P=NP.
So far, almost all of the problems that we have studied have had complexities that are
polynomial, i.e. whose running time T(n) has been O(n^k) for some fixed value of k. Typically k has been small, 3 or less. We will let P denote the class of all problems whose solution can be computed in polynomial time, i.e. O(n^k) or some fixed k, whether it is 3, 100, or something else. We consider all such problems efficiently solvable, or tractable. Notice that this is a very relaxed definition of tractability, but our goal in this lecture and the next few ones is to understand which problems are intractable, a notion that we formalize as not being solvable in polynomial time. Notice how not being in P is certainly a strong way of being intractable.
We will focus on a class of problems, called the NP-complete problems, which is a class of very diverse problems, that share the following properties: we only know how to solve those problems in time much larger than polynomial, namely exponential time, that is 2 O(n^k) for some k; and if we could solve one NP-complete problem in polynomial time, then there is a 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 you
recognize 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 solve
if n is large;
2. you can settle for approximating the solution, e.g. finding a nearly best solution rather than the optimum; or
3. 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 which there 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 problems in an approximate way in polynomial time (whereas an exact solution seems to require exponential time).
The other reason to study NP-completeness is that one of the most famous open problem in 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,1
one 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. After decades of research, everyone believes that P is not equal to NP, i.e. that no polynomial-time solutions for these very hard problems exist. But no one has proven it. If you do, you will be very
famous, and moderately wealthy.
So far we have not actually defined what NP-complete problems are. This will take some time to do carefully, but we can sketch it here. First we define the larger class of problems called NP: these are the problems where, if someone hands you a potential solution, then you can check whether it is a solution in polynomial time. For example, suppose the problem is to answer the question “Does a graph have a simple path of length |V |?”. If someone
hands you a path, i.e. a sequence of vertices, and you can check whether this sequence of vertices is indeed a path and that it contains all vertices in polynomial time, then the problem is in NP. It should be intuitive that any problem in P is also in NP, because are all familiar with the fact that checking the validity of a solution is easier than coming up with a solution. For example, it is easier to get jokes than to be a comedian, it is easier to have average taste in books than to write a best-seller, it is easier to read a textbook in a math or theory course than to come up with the proofs of all the theorems by yourself. For
all this reasons (and more technical ones) people believe that P not =NP, although nobody has any clue how to prove it. (But once it will be proved, it will probably not be too hard to understand the proof.)
The NP-complete problems have the interesting property that if you can solve any one of 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 are called complete. Thus, if you could show that any one of the NP-complete problems that
we will study cannot be solved in polynomial time, then you will have not only shown that P not =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, you will have shown that P=NP.
Comments
Post a Comment