still get the fame and the $1 million. It’s a mystery why people are still
trying to trisect the angle when it’s known to be impossible, when they
could be trying to find a polynomial-time algorithm for the traveling
salesman problem and become rich and famous for doing so.
Cook’s Tough Cookies
Cook came up with his idea in the early 1970s; by the late 1970s, more
than a thousand problems were known to be every bit as difficult to solve
as the scheduling problem or the traveling salesman problem. Admit-
tedly, many of these are minor variations of one problem, but it is worth
looking at some of the problems to realize how pervasive these really
tough problems are.
Satisfiability. This is the problem that Cook first examined. Recall that
propositional logic worked with compound statements such as IF (P AND
Q) THEN ((NOT Q) OR R). There are three independent variables in this
proposition: P, Q, and R. The problem is to determine whether there is an
assignment of the values TRUE and FALSE to the variables P, Q, and R
such that the compound statement above is TRUE. It’s not too hard to see
that all you need to do is let P be FALSE, then P AND Q must be false,
and any implication in which the hypothesis is FALSE must be TRUE.
The problem is that lengthier compound statements cannot be eyeballed
so easily.
The knapsack problem. Imagine that we have a collection of boxes with
different weights, and inside each box is an item with a given value. If the
knapsack can contain only a maximum weight W, what is the maximum
value of the contents of boxes that can be placed inside the knapsack?
There are two attractive greedy algorithms here. The first is to sort the
items in terms of decreasing value and start stuffing them into the knap-
sack, most valuable item first, until you can’t stuff any more inside. The
second is to sort the items in terms of increasing weight and start stuff-
ing them into the knapsack, lightest first, until you are forced to stop.
Remember moneyball, the idea that a team could be put together by
maximizing some quantity, such as most home runs hit last year per dol-
lar of current salary? There is a version of that which applies to the knap-
sack problem. One might sort the items in terms of decreasing value per
pound; this strategy might be described as “rare postage stamps first,” as
I believe rare postage stamps are the most valuable item on the planet as
measured in dollars per pound.
Graph coloring. The diagram used to illustrate tasks at the garage is
called a digraph, which is short for directed graph. A digraph is a collec-
164 How Math Explains the World