Tham khảo tài liệu 'thuật toán algorithms (phần 55)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | NP-COMPLETE PROBLEMS 533 running the given program on the given input so it produces a solution to an instance of the given problem. Further details of this proof are well beyond the scope of this book. Fortunately only one such proof is really necessary it is much easier to use reduction to prove NP-completeness. Some NP- Complete Problems As mentioned above literally thousands of diverse problems are known to be NP-complete. In this section we list a few for purposes of illustrating the wide range of problems that have been studied. Of course the list begins with satisfiability and includes traveling salesman and Hamilton cycle as well as longest path. The following additional problems are representative PARTITION Given a set of integers can they be divided into two sets whose sum is equal INTEGER LINEAR PROGRAMMING Given a linear program is there a solution in integers MULTIPROCESSOR SCHEDULING Given a deadline and a set of tasks of varying length to be performed on two identical processors can the tasks be arranged so that the deadline is met VERTEX COVER Given a graph and an integer N is there a set of less than N vertices which touches all the edges These and many related problems have important natural practical applications and there has been strong motivation for some time to find good algorithms to solve them. The fact that no good algorithm has been found for any of these problems is surely strong evidence that P NP and most researchers certainly believe this to be the case. On the other hand the fact that no one has been able to prove that any of these problem do not belong to P could be construed to comprise a similar body of circumstantial evidence on the other side. Whether or not P NP the practical fact is that we have at present no algorithms that are guaranteed to solve any of the NP-complete problems efficiently. As indicated in the previous chapter several techniques have been developed to cope with this situation since some sort of solution to
