Algorithmics - The Computing Universe: A Journey through a Revolution - page 98

Now let us go back to the traveling salesman problem. We have seen that
the brute force method to find the exact solution for the shortest path through
N cities grows like N!. A factorial grows with N much faster than any polyno-
mial. As we have seen, we can do better than this brute force solution. Using
dynamic programming, in 1962 Held and Karp found an algorithm that solves
an N-city TSP in a time proportional to N 2 2 N . 2 N corresponds to an exponen-
tial time complexity. Exponential growth occurs when the rate of growth of a
function is proportional to its current value. As can be seen from Figure 5.17 ,
exponential growth rapidly outstrips linear and quadratic growth, and in fact
outstrips any polynomial growth. This means that even though this algorithm
to find an exact solution for the traveling salesman problem is much better
than our brute force method, it is still unreasonable in that any computational
solution will take a time that grows exponentially with N. Any problem for
which we can find only exponential time algorithms is said to be intractable .

Table 5.3 Growth of operations for
sorting algorithms
N

10 50 100 300

N log 2 N 33 282 665 2469

N 2 100 2500 10000 90000

Does P = NP?

Before we leave the subject of algorithmics and complexity, we must intro-
duce one of the most difficult unresolved problems in computer science. It
turns out that the traveling salesman problem is representative of a large class
of problems that have unreasonable, brute force solutions but for which it can-
not be proved whether much faster, reasonable, algorithms exist. These prob-
lems are as diverse as devising a timetable to allocate teachers and courses to
classrooms with all sorts of constraints; packing items of varying sizes and
shapes into fixed-size bins; and determining possible arrangements of pat-
terned tiles. Finding some acceptable solution to even small versions of these
problems in real life usually involves much trial and error. After we have made
a choice that seemed to be the best possible choice at the time it turns out not
to be and we have to backtrack and try some other choice. All of these problems
have exponential time solutions, and no one has been able to find an algorithm
that solves any of these problems in polynomial time.
The problems in this class are called NP-complete . Computer scientists
denote the class of all problems that are tractable and have algorithms that
take only polynomial time by the symbol P. Besides only having known expo-
nential time solutions, the NP-complete problems have two other important
properties: they are nondeterministic, which is what N stands for, and they are
complete. To understand what these terms mean let us return to the traveling
salesman and pose the problem slightly differently by asking whether or not
we can find a tour with a length shorter than a given number of miles. As we
have seen, it is very difficult to find the shortest tour, but if we are given a spe-
cific tour, it is very easy to verify whether this tour is shorter than the specified
length. Where does the nondeterminism come in? Suppose we are trying to
find the shortest tour and start out at some city. There are some obvious possi-
bilities for the first step so we toss a coin to decide which city we should visit
first. If there are more than two cities to choose from we will have to toss the
coin more than once. We now suppose that the coin is not a normal one that
just gives a random result, but a “magical” one that always leads to the best
choice. The technical term for this magic is nondeterminism , and it means that

60

2 N N 2

50

40

N log 2 N

30

20

N

10

0

123456789 0
Problem size

Fig. 5.17. This graph shows the growth
with problem size N of four different
functions: N; N log 2 N; N 2 ; and 2 N . The
growth of an exponential function like
2 N is much faster than any polynomial
like N 2 .