Outer Limits of Reason (25 page)

is still exponential. So, quantum computers are not the hoped-for solution to the NP problems.

In summary, all foreseeable future improvements to computer technology are essentially impotent in the face of these NP problems. The only way that these problems will be easily solved is to find nice polynomial algorithms for them. We will show in the next section why most researchers believe that there are no better algorithms for these problems. It looks as though they will remain problems that cannot be solved in a reasonable amount of time. These problems are not hard because we lack the technology to solve them. Rather they are hard because of the nature of the problems themselves. They are
inherently
hard and will probably remain on the outer limits of what we can solve.

5.3  They're All Connected

In the last section, we encountered several problems whose only known algorithms are brute-force searches, which take way too much time. At this point , no one has a polynomial algorithm to solve any of them. That is, no one has any easy trick to find a solution in a shorter amount of time. In this section, we will learn why most researchers believe that no such polynomial algorithms exist.

If you spend a little time working on the Set Partition Problem and the Subset Sum Problem, you will find that they are very similar and are, in fact, related. We can easily transform an instance of the Set Partition Problem into an instance of the Subset Sum Problem. The idea is that in the Set Partition Problem, you are really looking for a single subset of the elements that sum to half of the sum of all the elements in the set. For example, consider the set {12, 63, 13, 82, 42, 54, 24, 76, 22}. One way to determine if this set can be partitioned into two sets with equal sums of elements is to see if there is a subset that sums to half of the sum of all the elements. In this case, we would have to determine if there is a subset whose elements sum to

C =
(12 + 63 + 13 + 82 + 42 + 54 + 24 + 76 + 22) / 2 = 388 / 2 = 194.

If such a subset exists, then the set can be partitioned into those elements in the subset and those elements not in the subset. If there is no such subset that sums to 194, then this instance of the Set Partition Problem yields a negative answer.

What we are saying here is that if we can solve the Subset Sum Problem, then we can most definitely solve the Set Partition Problem. In our notation:

solve Subset Sum Problem ⇒ solve Set Partition Problem.

If you have an instance of the Set Partition Problem, just transform the problem into a Subset Sum Problem as we did above by setting
C
to be half of the sum of all elements in the set. To say that if you can solve one problem, then you can definitely solve a second problem means that the first problem is as hard or harder than the second. So we showed that the Subset Sum Problem is as hard or harder than the Set Partition Problem. In other words, the Set Partition Problem is as hard as or easier than the Subset Sum Problem. We write this as follows:

Set Partition Problem ≤
_P
Subset Sum Problem.

Let us generalize what we just did for two arbitrary decision problems. Imagine that we have a Problem B that a computer can solve. This means we have a machine into which we input an instance of the problem and it will output either a Yes or No depending on the solution. We might represent this with
figure 5.11
. The input enters at the left and the machine calculates and outputs either a Yes or No.

Now imagine that we have a Problem A. If there is a way of transforming an instance of Problem A into an instance of Problem B, we can create a machine that decides Problem A by connecting the transformer to the Problem B decider as in
figure 5.12
.

An instance of Problem A enters on the left. The instance is transformed into an instance of Problem B and then goes into a Problem B decider to give an answer to both problems.

We don't want the transformer to arbitrarily change an instance of Problem A into an instance of Problem B. We require that the instances have the same answer. In other words, we will insist that the transformer take inputs with a “Yes” answer for Problem A to inputs that answer “Yes” for Problem B. If an input to Problem A gets a “No” answer from the Problem A decider, the transformer should output an instance that will have a “No” answer. We make one further requirement: this transformer should perform its task in a polynomial amount of operations. The need for this stipulation will quickly become apparent.

When we have such a relationship between Problem A and Problem B, we say that we have a “reduction of Problem A to Problem B” or “Problem A reduces to Problem B.”

Let us look at another example of a reduction of one problem to another. The Hamiltonian Cycle Problem is reducible to the Traveling Salesman Problem. Consider the instances of the Hamiltonian Cycle Problem given in
figure 5.10
. We convert them into instances of the Traveling Salesman Problem in
figure 5.13
. Bear in mind that the Traveling Salesman Problem demands complete and weighted graphs. We complete the graphs by adding edges between those vertices that were not already connected. To differentiate among the types of edges, we will make the new edges gray.

As for the weights, we say that all black edges have weight 0 and all gray edges have weight 1. And now for the final ingredient to make this an instance of the decision version of the Traveling Salesman Problem: we set the required integer K to 0. If there exists a traveling salesman cycle that has weight (less than or) equal to 0, none of the new gray edges were used in the cycle, so there was a Hamiltonian cycle in the original graph. The left graph in
figure 5.13
contains such a traveling salesman cycle and the graph on the right does not. We have successfully reduced the Hamiltonian Cycle Problem to the Traveling Salesman Problem.

Why does it help us to know whether one hard problem can be reduced to another? After all, both problems are effectively unsolvable for any large
n.
In the next few pages, we will see many reasons why this concept of reduction is fundamental to the entire field of study.

Let us ponder this situation a bit. Imagine that NP Problem A can be reduced to NP Problem B, that is, Problem A ≤
_p
Problem B. Now imagine that some supergenius comes out of nowhere with some fancy newfangled algorithm that can actually solve Problem B in polynomial time. This super-genius will no doubt earn many accolades for finally finding an easy way of solving Problem B. Those who waited for trillions of centuries while some exponential algorithm solves problem B can “break out” of that algorithm and run the new polynomial algorithm, getting a result in minutes.

But there is more. With a polynomial reduction, not only will the supergenius get credit for solving Problem B, but Problem A will also be solved in polynomial time. To solve Problem A in polynomial time, all one has to do is put an instance of Problem A through the polynomial transformer to get an instance of Problem B, then put that instance into the supergenius' new polynomial algorithm. Since the transformer only takes a polynomial amount of time and the new algorithm is also done in polynomial time, the entire process can be done in a-polynomial-plus-a-polynomial amount of time. The addition of two polynomials is a polynomial and so the entire process can be done in a relatively short time. So our supergenius will be praised not only for solving problem B, but also for solving
any other
problem that can be reduced to problem B.

To understand the relationship between two problems that are linked to each other, let us compare it to climbing two mountains. Since Mount Everest is taller than Mount McKinley, the following statement is true:

If you can climb Mount Everest, then you can definitely climb Mount McKinley.

That means that it is harder to climb Mount Everest than Mount McKinley. This is equivalent to saying:

If you cannot climb Mount McKinley, then you definitely cannot climb Mount Everest.

Similarly, when there is a polynomial reduction from Problem A to Problem B, the following statement is true:

If Problem B can be solved in polynomial time, then Problem A can also be solved in polynomial time.”

That means that Problem B is harder than or as hard as Problem A. This statement is equivalent to:

“If Problem A cannot be solved in polynomial time, then Problem B also cannot be solved in polynomial time.

Until now, we have spoken about an NP problem that has another NP problem reducible to it. Now let's talk about an NP problem such that
every
NP problem is reducible to it. An NP problem such that every NP problem is reducible to it is called an
NP-Complete
problem. In a sense, NP-Complete problems are the hardest NP problems. All five problems presented in
section 5.2
are, in fact, NP-complete problems and are reducible to one another.

Since any other NP problem is reducible to an NP-Complete one, if any NP-Complete problem can be solved in polynomial time, then all NP problems can be solved in polynomial time.

With the notion of NP-Complete problems, one can see why researchers believe that polynomial algorithms to solve such problems will never be found. Take any NP-Complete problem, say the Traveling Salesman Problem. For many years, people have looked in vain for a polynomial algorithm to solve this problem. This section has demonstrated the interconnectedness of the NP-Complete problems. If any person had found a polynomial algorithm for
any
NP-Complete problem, then the Traveling Salesman Problem would also have a polynomial solution. In a sense, researchers working on any NP-complete problem have also been working on the Traveling Salesman Problem. So we can say that thousands of people have been seeking a polynomial algorithm for our problem for many years and so far have found nothing. It seems likely that no such algorithm exists.