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.

Mon Jun 2 23:33:50 EDT 1997