The Algorithm Design Manual Second Edition

Chapter Notes

The notion of NP-completeness was first developed by Cook

[Coo71]

. Satis-

fiability really is a $1,000,000 problem, and the Clay Mathematical Institute

has offered such a prize to any person who resolves the P=NP question. See

http://www.claymath.org/ for more on the problem and the prize.

Karp

[Kar72]

showed the importance of Cook’s result by providing reductions

from satisfiability to more than 20 important algorithmic problems. I recommend

Karp’s paper for its sheer beauty and economy—he reduces each reduction to three

line descriptions showing the problem equivalence. Together, these provided the

tools to resolve the complexity of literally hundreds of important problems where

no efficient algorithms were known.

The best introduction to the theory of NP-completeness remains Garey and

Johnson’s book Computers and Intractability. It introduces the general theory,

including an accessible proof of Cook’s theorem

[Coo71

] that satisfiability is as

hard as anything in NP. They also provide an essential reference catalog of more

than 300 NP-complete problems, which is a great resource for learning what is

known about the most interesting hard problems. The reductions claimed, but

missing from this chapter can be found in Garey and Johnson, or textbooks such

as

[CLRS01]

.

A few catalog problems exist in a limbo state where it is not known whether

the problem has a fast algorithm or is NP-complete. The most prominent of these

are graph isomorphism (see Section

16.9

(page

550

)) and integer factorization (see

Section

13.8

(page

420

)). That this limbo list is so short is quite a tribute to the

state of the art in algorithm design and the power of NP-completeness. For almost

every important problem we either have a fast algorithm or a good solid reason for

why one doesn’t exist.

The war story problem on unidirected subgraph was originally proven hard in

[Mah76]

.