Outer Limits of Reason (26 page)

Why is it important to show that some problem is NP-Complete? Two vital reasons are usually given. First, by showing that a problem is NP-Complete, we are demonstrating that finding an efficient algorithm for this problem is as hard as finding such an algorithm for other NP-Complete problems. Since no one has been able to find an efficient algorithm for any NP-Complete problem, we are showing that the problem is inherently hard. If you were given the job of writing a nice polynomial algorithm to solve a problem and you have a hard time completing the task, you will find yourself in trouble with your boss. If, however, you show the problem is NP-Complete, you can insist that not only are you unable to find a good algorithm, but no one else can either. This claim will save your job.

Another reason why the concept of NP-Complete problems is important is that once it is known that a problem cannot be easily solved, we are free to move on to find other algorithms that might help us
approximate
a solution to the problem. Algorithms that approximate solutions in a reasonable amount of time are introduced in
section 5.4
.

Once one has an NP-Complete problem, it is not hard to find others. If A is a known NP-Complete problem and you are interested in showing that B is an NP-Complete problem, you need only perform the following two tasks:

1. Show that B is NP.

2. Show that A ≤
_P
B—that is, that B is as hard as or harder than A.

From the fact that A is a known NP-Complete problem, and all NP problems are reducible to A, and from the fact that A is reducible to B, we know that all NP problems are reducible to B. This can be seen in the figure 5.14, in which we draw an arrow from one problem to another if there is a reduction between them.

To recap: once we have one NP-Complete problem, we can easily find others. But how does one find the
first
NP-Complete problem? In the early 1970s, Stephen Cook of North America and Leonid Levin of Russia independently proved that the Satisfiability Problem is an NP-Complete problem. This theorem, which came to be known as the
Cook-Levin Theorem
, is one of the most amazing theorems in computer science. The theorem states that
all
NP problems can be reduced to the Satisfiability Problem. We have seen five diverse NP problems. There are currently thousands of known NP problems, some about graphs, some about numbers, some about DNA sequencing, some about scheduling tasks, and so on. These problems come in many different shapes and forms, and yet they are all reducible to the Satisfiability Problem. But wait . . . there's more! Cook and Levin did not demonstrate that every NP problem now in existence is reducible to the Satisfiability Problem; rather, they showed that
all
NP problems—even those not yet described—are reducible to the Satisfiability Problem.

The way Cook and Levin showed that the Satisfiability Problem is NP-Complete is clever and worth understanding. They started by asking what all NP problems have in common. By definition, every NP problem can be solved by a computer in at most an exponential or factorial number of operations. Now ask how such a computer works. What is the inner core of computers? The answer is simple: computers and their chips follow the laws of logic. Inside every computer there are literally billions of logical switches that perform the logical operations AND, OR, NOT, and IMPLY.
⁸
So since every NP problem can be solved by a logical computer, every NP problem can be reduced to the Satisfiability Problem. We kicked off this chapter with a discussion of how computers are engines of logic and reason. We now see that clearly. Every computer problem can be changed into a logical expression.

 

Before I end this section, let me tell you how to make a million dollars. At the turn of the millennium, in order to promote mathematics, the Clay Institute declared seven problems in mathematics to be the most important and hardest of their kind. Anyone who solves one of these “Millennium Problems” will receive a million dollars. One of these problems is the
P
=?
NP
problem or “is
P
equal to
NP
?” We saw at the end of
section 5.2
that
P
is a subset of
NP
—that is, every easy problem can be solved in less than a large amount of time. But we can ask the reverse: Is
NP
a subset of
P
? Is it possible that every hard NP problem can be solved in a polynomial amount of time? If
NP
is a subset of
P
, then
P
=
NP
. If
NP
is not a subset of
P
, then there is a problem in
NP
that is not in
P
and
P
≠
NP
. The two possibilities are depicted in
figure 5.15
. To win the prize, all you have to do is prove the answer one way or the other.

How should you go about claiming your award money? There are two possible directions to take. You can try to prove that
P
=
NP
or you can aim to show that
P
≠
NP.
⁹
To show that
P
=
NP
, all you have to do is take one of your favorite NP-Complete problems and find a polynomial algorithm that solves it. As we have seen, if you do find such an algorithm, then all NP problems will be solvable in a polynomial amount of operations. It might seem strange to think that a problem that demands an exponential or factorial amount of operations can be done in a polynomial amount of operations. However, we saw something similar with the Euler Cycle Problem. Rather than look through all
n
! possible cycles to see if any are Euler cycles, we used the trick of checking if the number of edges touching each vertex is even or not. Does a similar trick for the Hamiltonian Cycle Problem exist? For many years, the smartest people around have been looking for such a trick or algorithm and have not been successful. However, you might possess some deeper insight that they lack. Get to it!

On the other hand, you can try to show that
P
≠
NP
. One way to do this is to take an NP problem and show that no polynomial algorithm exists for it. It so happens that it is very hard to prove such a claim: there are a lot of algorithms out there. This has turned out to be one of the hardest problems in mathematics.
¹⁰
As a final hint, it should be noted that most researchers believe that
P
≠
NP
.

5.4  Almost Solving Hard Problems

These NP-Complete problems are not abstractions that computer scientists and mathematicians created. They come from real-world applications and are problems that need to be solved. Industry and computer professionals are always looking to find efficient solutions to these problems. Waiting several centuries for the answers is not acceptable.

To deal with these problems, computer scientists have invented helpful algorithms that will eliminate some of the pain of harder problems. Such algorithms are referred to as “approximation algorithms.” These algorithms require a polynomial number of operations but do not always give the correct answer. Sometimes they are off by a little, sometimes by a lot.

Approximation algorithms are usually based on heuristics. These are recommendations that one learns through experience and are like “rules of thumb”—not always 100% correct but “close enough” to the solution.

Consider the traveling salesman problem, which is probably the most intuitive of the NP-Complete problems mentioned in
section 5.2
. Let's go back to the major-cities problem presented at the beginning of that section. Say the salesman starts in Los Angeles. From there, he does not think of the entire route that he needs to take; rather, he just determines the closest city on the list. The nearest city is San Francisco. Once he gets to San Francisco, again he looks for the nearest city he did not visit: Denver. And again, once he comes to each city, he simply looks for the nearest city he has not yet visited. This is an intuitive way of dealing with the problem. The traveler does not look at the “big picture.” Rather he greedily picks the nearest city. This method is called the “nearest neighbor heuristic.” At each vertex, simply go to the closest neighbor possible. This algorithm always works in a polynomial amount of time. However, it does not always find the correct solution.

While the nearest neighbor heuristic seems as though it will always find the correct solution, in actuality, it fails and it is easy to see why. Consider the complete weighted graph given in
figure 5.16
. Only the weights of neighboring edges are given, but the other weights can be calculated from them.

Suppose we forced the traveler to start at vertex a. By the nearest neighbor heuristic, she would have to go to vertex b, which is only one mile away. From vertex b, the traveler would have two choices: either c, which is four miles away, or e, which is three miles away.
¹¹
By our algorithm, she must choose e. Once the traveler is at e, she must go to c. By following the nearest neighbor heuristic, the traveler must make the following cycle:

a → b → e → c → f → d → a.

Our poor traveler would have to travel

1 + 3 + 7 + 15 + 31 + 21 = 78 miles.

As we mature, we learn that going through life taking shortcuts will not always get you to where you want to go in the shortest amount of time. Sometimes shortcuts will lead you astray. Consider this cycle, which does not follow the nearest neighbor heuristic:

a → b → c →d → f → e → a.

This cycle will need

1 + 4 + 16 + 31 + 8 + 2 = 62 miles.

Clearly, the nearest neighbor heuristic did not work very well for this complete weighted graph.

What about the Set Partition Problem? Here is a polynomial approximation algorithm that I call
extreme pairs
. Given a set of numbers, {24, 68, 61, 41, 35, 51, 58, 39, 49 54, 29, 23}, sort the elements as follows:

23, 24, 29, 35, 39, 41, 49, 51, 54, 58, 61, 68.

Take the pair of extreme elements, the minimum and maximum (23 and 68), and put them in one partition. Put the remaining minimum and the maximum (24 and 61) into the other partition. Continue in this manner until every element is in one of the partitions. This will leave us with

The left-hand partition sums to 268, while the right-hand partition sums to 264.
¹²
Is there a better solution?

It's worth taking a few minutes to see why the extreme-pairs algorithm works. Take the sequence of numbers in order as in
figure 5.17
.