The Algorithm Design Manual Second Edition

343

9.9.3

Why is Satisfiability the Mother of All Hard Problems?

An enormous tree of NP-completeness reductions has been established that entirely

rests on the hardness of satisfiability. The portion of this tree demonstrated and/or

stated in this chapter (and proven elsewhere) is shown in Figure

9.2.

This may look like a delicate affair. What would it mean if someone does find

a polynomial-time algorithm for satisfiability? A fast algorithms for any given NP-

complete problem (say traveling salesman) implies fast algorithm for all the prob-

lems on the path in the reduction tree between TSP and satisfiability (Hamiltonian

cycle, vertex cover, and 3-SAT). But a fast algorithm for satisfiability doesn’t im-

mediately yield us anything because the reduction path from SAT to SAT is empty.

Fear not. There exists an extraordinary super-reduction (called Cook’s theorem)

reducing all the problems in NP to satisfiability. Thus, if you prove that satisfiability

(or equivalently any single NP-complete problem) is in P , then all other problems

in NP follow and P = N P . Since essentially every problem mentioned in this book

is in NP, this would be an enormously powerful and surprising result.

Cook’s theorem proves that satisfiability is as hard as any problem in NP.

Furthermore, it proves that every NP-complete problem is as hard as any other. Any

knocks them all down. Our inability to find a fast algorithm for any of these

problems is a strong reason for believing that they are all truly hard, and probably

P

= NP .