The Importance of the P vs. NP Problem

The "P vs. NP" question is the most important open question in the complexity theory of mathematics today, and not just a difficult question of trivial consequence. I will give an overview of the P vs. NP problem, and go on to show how important it is to the world we live in today.

In complexity theory, mathematicians separate all problems into classes which describe how much calculation is required to solve them (roughly speaking, by how "complex" they are). The number of calculations required to solve any given problem is shown as a function of the problem's input size (n). If the number of calculations required to solve the problem can be written as some polynomial of n (such as xny+z | x, y, and z are constants), then the problem is said to be of class P. If the number of calculations required to solve the problem can only be written as an expression with n showing up as a power of a polynomial (such as xyn+z | x, y, and z are constants) or with the expression n! (n! means "n factorial." This means 1*2*3*4*…(n-3)*(n-2)*(n-1)*n), then the problem is said to be of class NP (which means the problem can only be solve in "nondeterministic-polynomial time"). To over simplify just a little, one could say that P problems are easy, and NP problems are hard (Delvin).

Here is an example of a problem of class P: In a room with n number of people, how many handshakes must occur if each person is to shake every other person's hand? Well, the first person will have to shake (n-1) hands. The next will have to shake (n-2) people's hands. The next will have to shake (n-3), and so on until there are only two people left. The second to last person will shake the last person's hand, and the handshaking will be over. So, the solution to this problem is always 1+2+3+4+5+…+ (n-2) + (n-1). So, to solve this problem we must make (n-1) addition calculations. Thus, the complexity of this handshake problem is n-1, which puts it in complexity class P.

Here is another example, this time of a problem of class NP: A salesman has an itinerary with n cities. He needs to travel to every city on the list (only visiting each city once), then return home. He wants to take the shortest route possible. Which route is his shortest route? Currently, the only known way to solve this problem is to list every possible route given the salesman's list, total up the mileage for each of those routes, then search the list for the shortest route on the list. If there are n cities on the salesman's list, this means that the number of possible routes is equal to n!. For each of those routes we will need to add up n distances between cities. We will also need to compare all n! sums to see which is of the shortest distance. Thus, in order to solve this problem, we will need to make (n!*n)+n! calculations. This means that the "Traveling Salesman" problem is certainly in class NP (Delvin) (Garey, Johnson).

This side by side comparison may illustrate the problem a little more clearly. Here is a table with different input sizes (i.e.: values of n) and the corresponding number of calculations required to solve the problems:

Input size (n): 5 10 20
Handshake problem (P): (4) (9) (19)
Traveling Salesman problem (NP): (720) (39,916,800) (51,090,942,171,709,440,000)

As you can see, the number of calculations required to solve NP problems grow drastically more quickly than do problems of class P. It took a team of mathematicians over 30 days, using one of the fastest super computers available, to solve an instance of the Traveling Salesman problem with only 30 cities involved (Delvin).

Many problems of significant value are NP-complete. Problems which are said to be NP-complete are ones which have been proven to be mathematically equivalent to another NP-complete problem. In other words, since the Traveling Salesman problem is NP-complete, that means any instance of the Traveling Salesman problem can be mathematically turned into an instance of any other NP-complete problem (Claymath.org). There are hundreds of problems that have been shown to be NP-complete. Among them are: the next best move in a chess game, deciphering RSA cryptography (used often in electronic banking security, as well as military operations), the computer game Minesweeper, the Subset-sum problem, the Boolean-Circuit problem, etc.

Because all of these hundreds of problems are mathematically equivalent, if some clever person finds a way of solving any one of them in polynomial time, a mathematician will be able to apply that same algorithm to every single other NP-complete problem. That means that a fast solution to one NP-complete problem is a fast solution to all NP-complete problems (Claymath.org). It's amazing to think that an algorithm which can solve any instance of minesweeper in polynomial time would be easily transformed into an algorithm capable of crippling Internet and military security just as quickly.

So, what is the P vs. NP problem? It simply asks, is there any way to turn class NP problems into class P problems? Or is it simply impossible? Remember, the only reason why calculating the shortest route that passes through 20 cities requires 51,090,942,171,709,440,000 calculations, is because no faster algorithm has been devised that can solve it faster than calculating the distances of every possible route and comparing them to determine which is shortest. Can some clever person come up with an algorithm that solves NP problems in polynomial time? If you are the one to do it, or even the one who can prove that it cannot be done, then you could be the recipient of a $1,000,000 prize. The Clay Mathematics Institute is offering the prize in hopes of advancing the understanding of mathematics (Claymath.org). They are not the only ones interested. The NSA frequently attends the lectures of pure mathematicians who are trying to advance the subject (Delvin).

A solution to the P vs. NP problem could have huge impacts in areas such as weather prediction, economic forecasting, efficient distribution and transportation, the very future of cryptography, molecular modeling, etc. If a positive solution to P vs. NP is found (i.e. one that solves NP problems in polynomial time), wars will be fought differently, and business will be conducted differently as well. A positive solution to P vs. NP would have results that would make the entire Internet a mere footnote in modern history (Delvin).

A negative solution - one that proves that NP problems will not ever be able to be solved in polynomial time - will let deep-cover spies and bank owners sleep better at night, knowing that their codes are safe, and they cannot be broken without a huge stroke of luck. About 60% of mathematicians and computer scientist interviewed believe that a negative solution will be found (Delvin).

In conclusion, you have learned about complexity classes P and NP, and you now have a better understanding of the P vs. NP problem. With all of this new information, I'm sure you will agree that the P vs. NP problem is the most important open question in the complexity theory of mathematics today. Knowing how much is at stake, I'm sure you can see that this problem is not just a difficult question of trivial consequence.

Works Cited

Keith Devlin The Millennium Problems
Granta Books, December 31, 2003

M. R. Garey, D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness
W. H. Freeman, January 15, 1979

"Millennium Problems" Claymath.org 17 Nov. 2006
Clay Mathematics Institute 2006 http://www.claymath.org/millennium

"P vs. NP Problem" Claymath.org 2006
Clay Mathematics Institute 2006 http://www.claymath.org/millennium/P_vs_NP

"Ian Stewart on Minesweeper" Claymath.org 2006
Clay Mathematics Institute 2006 http://www.claymath.org/Popular_Lectures/Minesweeper