8.1 WHAT IS NP? 219We show that a problem is NP-complete by showing that every other prob-
lem in the class NP can be transformed into it. This is not as daunting of a task
as it sounds because we don’t have to do this for every NP problem. Instead, if
we have an NP problem A, we can show that it is NP-complete by reducing an
NP-complete problem B into it. Because B is NP-complete, every problem in
NP can be transformed into problem B. So, by reducing B to A, we effectively
show that all NP problems can be transformed into A by a two-step process
that first transforms them to B. Therefore, our NP problem A is now known to
be NP-complete.
In the last section we did a reduction of a polynomial time algorithm; now
we do one for an NP problem. We need a process that will modify all of the
components of one problem so that they become an equivalent component in
another problem. This transformation must preserve the information so that
every time the first problem gives a positive result so does the transformed
problem, and every time the first problem gives a negative result so does the
second problem.
In a graph, a Hamilton path is one that visits every node of the graph
exactly once. If the path returns to the starting node, it is called a Hamilton
circuit. A graph doesn’t need to be complete for it to have a Hamilton path or
circuit. We can reduce the Hamilton circuit problem to the traveling salesper-
son problem in the following way. Each node in the graph becomes a city. For
each edge in the graph, we assign the cost of traveling between the two equiv-
alent cities a value of 1. For each pair of nodes that have no edge connecting
them, we assign the cost of traveling between the two equivalent cities a value
of 2. This converts the graph into a set of cities. We now solve the related trav-
eling salesperson problem. If there is a Hamilton circuit in the graph, the trav-
eling salesperson problem will be able to find a solution traveling between
cities that just have costs of 1. If there is no Hamilton circuit, the solution the
traveling salesperson problem finds will travel between at least one pair of cities
with a cost of 2. If there are N nodes in the graph, there is a Hamilton circuit if
the traveling salesperson path is of length N, and there is no Hamilton circuit if
the path is of length greater than N.
In 1971, Cook showed that the CNF-satisfiability problem described in the
next section was NP-complete. A large number of additional problems have
been shown to be NP-complete by reducing the satisfiability problem, or