Next: 3-Satisfiability Up: Satisfiability Previous: Satisfiability

## The Theory of NP-Completeness

For a variety of social and technical reasons, it is well accepted that satisfiability is a hard problem, one for which no worst-case polynomial-time algorithm exists. Literally every top-notch algorithm expert in the world (and countless lesser lights) has directly or indirectly tried to come up with a fast algorithm to test whether a given set of clauses is satisfiable, but all have failed. Further, many strange and impossible-to-believe things in the field of computational complexity have been shown to be true if there exists a fast satisfiability algorithm. Satisfiability is a hard problem, and it is important to accept this. See Section for more on the satisfiability problem and its applications.

The theory of NP-completeness rests on a foundation of rigorous but subtle definitions from automata and formal language theory. This terminology is typically confusing to or misused by beginners who lack a mastery of these foundations, and it is not really essential to the practical aspects of designing and applying reductions. For completeness, however, we briefly define the key terms below.

A problem is said to be polynomial (or in the class P) if it can be solved in time polynomial in its size. A problem is said to be nondeterministically polynomial (or in the class NP) if a conjectured answer can be verified in time polynomial in its size. The traveling salesman decision problem is not known to be in P, because there is no known polynomial-time algorithm for it. However, the problem is in NP, because if we are given a candidate tour, we can efficiently add up the cost of the associated edges and verify whether the total is at most the cost bound k. It is typically straightforward to verify whether the answer to a problem is correct, and it certainly can be no harder than actually finding the answer in the first place.

Through a complicated proof, it has been established that satisfiability is at least as hard as any problem in NP. This means that if a fast (i.e. polynomial-time) algorithm is discovered for solving satisfiability, this will yield a fast algorithm for every problem in NP. Since essentially every problem mentioned this book is in NP, this would be an enormously powerful and surprising result. We say that a problem is NP-hard if, like satisfiability, it is at least as hard as any problem in NP. We say that a problem is NP-complete if it is NP-hard, and also in NP itself. Because NP is such a large class of problems, most NP-hard problems you encounter will in fact be complete, and the issue can always be settled by giving a (usually simple) verification strategy for the problem.

Next: 3-Satisfiability Up: Satisfiability Previous: Satisfiability

Algorithms
Mon Jun 2 23:33:50 EDT 1997