 Teacher resources and professional development across the curriculum

Teacher professional development and classroom resources across the curriculum  # 2.8 P=NP

## THE TRAVELING SALESPERSON

• The problem of how to find the shortest Hamilton cycle on a weighted graph has many variations, and the task gets very difficult very quickly as the graph gets bigger.

Imagine that you are a traveling salesperson and you must visit multiple cities to make your calls. Because you are responsible for covering the costs of travel, you are probably quite interested in planning a route that takes you to each city once with the minimum amount of travel.

This problem is similar to the sequencing problems of the previous section, except that now not all connections are equal. Such graphs are known as "weighted graphs" and are somewhat more difficult to deal with than the morebalanced graphs we have seen before. With a small number of cities, this problem is not difficult to figure out. Let's say that you can start at any city you choose, but you have to return to the same city to complete the cycle. It should be evident by now that the number of possible routes will be (n-1)! So, for four cities, you will have six optional routes to check. So, this problem quickly becomes a fairly simple exercise in finding the distance for each route and choosing the shortest. However, suppose you decide to add another city to your route. Now you have twenty-four possible routes to investigate—a bigger problem, but still doable. If you would add yet another city, you would have 120 possible routes to consider. This is quickly becoming time-consuming! At this point, it would make sense to use a computer. We could program the computer to enumerate every route, find their sums (total travel distances), and then sort the routes by length. As we keep adding cities to our sales itinerary, we could use our computer to check each route, but even with as few as ten cities we would have to check about 350,000 million routes. Twenty cities would involve checking approximately 1017 routes. Even using our simple algorithm on a fast computer will not enable us to find such a solution in any realistic amount of time. This is an example of factorial time.

## DIFFERENT TYPES OF TIME

• How a problem scales, that is, how it changes as it involves more elements, can be measured by how much time it takes an algorithm to solve it.
• Feasible problems can be solved in polynomial time.

Some problems can be solved in what is known as "polynomial time." Multiplying two numbers is an example of this. If you multiply two six-digit numbers, it will not take appreciably longer than multiplying two five-digit numbers. For example, long multiplication of two three-digit numbers requires approximately nine operations. Long multiplication of two five-digit numbers requires approximately twenty-five operations. In general, multiplying two n-digit numbers commonly requires n2 operations. An algorithm in which the number of steps, n, is a polynomial (such as n2 or (37n4-3n3+n-1) in the size of the input is called a P-method. P-method problems can be solved in what is known as "polynomial time."

The problem of the traveling salesperson actually grows more quickly than this—it grows in factorial time. There are various methods for solving such problems. Some involve heuristic algorithms, which, although they may be quick some of the time, are not dependably quick. Other techniques can achieve approximate solutions quickly within a specified tolerance of the optimal solution. Another, theoretical way to solve this type of problem would be to use a computer that is a "lucky guesser." Such a computer would, by making lucky guesses, find the ideal answer in polynomial time. Problems that can theoretically be solved in polynomial time only by such a "lucky" computer are known as NP. Note that the "lucky computer" method doesn't really exist as a way of solving problems. It's a theoretical construct used to distinguish different types of computing problems, namely to define the NP class of problems. Technically, the lucky computer isn't solving the problem as stated—it is merely verifying that its guess is correct, which presents a slightly different problem.

## DOES P = NP?

• The question of whether or not NP problems are really P problems in disguise is still outstanding.

There are many problems similar to that of the traveling salesperson. Packing boxes of different sizes into a confined space, such as when you pack to move or go on vacation, is an example. The situations encountered when playing Tetris can be transformed into the equivalent of the traveling salesperson problem. All of these problems can be turned into one another, and all of these could be theoretically solved in polynomial time by a "lucky" computer. Such problems are known as NP-complete problems.

Because every NP-complete problem can be turned into every other NP-complete problem, if someone were to find a P-method to solve one of them, then there would be a P-method to solve all of them. This leads to the question: Are all NP problems really just P problems in disguise?

This question is one of the major outstanding issues in mathematics, computing, and complexity theory. It is also one of the Clay Mathematical Institute's Millennium Problems. Any person who either shows that P = NP, perhaps by finding a P-method to solve the traveling salesperson problem, or proves that P does not equal NP, will win \$1,000,000.