Definition 14.4
A language L is said to be NP-complete if L ∈ NP and every L 1 ∈ NP is
polynomial-time reducible to L.
It follows from this definition that if L is NP-complete and polynomial-time
reducible to L 1 , then L 1 is also NP-complete. So if we can find one deterministic
polynomial-time algorithm for any NP-complete language, then every language
in NP is also in P, that is,
P = NP.
Here we hold out the hope that efficient algorithms exist for such problems, even
if none have been found yet. On the other hand, if one could prove that any of
the many known NP-complete problems is intractable, then many interesting
problems are not practically solvable. This puts NP-completeness in the center
of the question of the tractability of many important problems. At this point then,
we need to study some NP-complete problems. The next result, known as
Cook's theorem, provides the entry point to this study.
Theorem 14.5
The Satisfiability Problem(SAT) is NP-complete.
Proof: The idea behind the proof is that for every configuration sequence of a
Turing machine one can construct a CNF expression that is satisfiable if and
only if there is a sequence of configurations leading to acceptance. The details,
unfortunately, are long and complicated. They are technical and shed little light
on the NP problem, so we will omit them here. Extensive discussions of Cook's
theorem can be found in books devoted to complexity.
If we accept Cook's theorem, we immediately have a number of NPcomplete problems.
Example 14.11