The Algorithm Design Manual Second Edition

317

9.1

Problems and Reductions

We have encountered several problems in this book for which we couldn’t find any

efficient algorithm. The theory of NP-completeness provides the tools needed to

show that all these problems are on some level really the same problem.

The key idea to demonstrating the hardness of a problem is that of a reduction,

or translation, between two problems. The following allegory of NP-completeness

may help explain the idea. A bunch of kids take turns fighting each other in the

schoolyard to prove how “tough” they are. Adam beats up Bill, who then beats up

Chuck. So who if any among them is “tough?” The truth is that there is no way

to know without an external standard. If I told you that Chuck was in fact Chuck

Norris, certified tough guy, you have to be impressed—both Adam and Bill are at

least as tough as he is. On the other hand, suppose I tell you it is a kindergarten

school yard. No one would call me tough, but even I can take out Adam. This

certifiably hard problem. The part of an inefficient algorithm with a possible shot

at redemption is played by me.

Reductions are operations that convert one problem into another. To describe

them, we must be somewhat rigorous in our definitions. An algorithmic problem is

a general question, with parameters for input and conditions on what constitutes a

satisfactory answer or solution. An instance is a problem with the input parameters

specified. The difference can be made clear by an example:

Problem: The Traveling Salesman Problem (TSP)

Input: A weighted graph G.

Output: Which tour

{v

1

, v

2

, ..., v

n

} minimizes



n

−1

i=1

d[v

i

, v

i+1

] + d[v

n

, v

1

]?