Saturday, January 1, 2011

P=NP and the million dollar mathematics prize

The Clay Mathematics Institute in Cambridge Massachusetts is providing a one million dollar prize for the first person who can prove or disprove the P=NP problem. A variety of descriptions of the P=NP problem are available. Simply put, computer scientists have divided computer problems into a series of categories which include P (problems that are relatively easy to solve) and NP (problems that are relatively challenging to solve). The majority of computer scientists believe that P != NP (P is not equal to NP - this expression is repeated below) indicating that many believe problems exist which are too complex to solve for them to ever be classified as P type problems. Recently Vinay Deolalikar of HP labs released a possible proof that P != NP. His work has been subject to some criticisms, however, I am inclined to agree with his goal of proving that P != NP and good luck to him in responding effectively to his critics - that million dollar prize would sure be sweet!

I was thinking about this problem in a general sense - no messy mathematics should be necessary for this discussion. If a problem is thought to be NP and thus unsolveable in an efficient amount of time, and then someone invents a new method for solving that problem algorithmically in an efficient amount of time then that merely would show that that particular problem was not in fact an NP problem at all, it was a P problem lacking an effective method for solving the problem. If an NP problem turns out to be solvable in a reasonable amount of time (in the time it takes to solve a P problem), then we should just call it a P problem.

It is highly doubtful that a new algorithmic development will ever solve all problems currently accepted as being NP problems within the time frame associated with P problems. One day all or most of those problems will be solved quickly, however, that will be done with the help of faster computers or even alternative architectures that wouldn't even be what we call today a standard computer. Algorithmic developments are sure to help, however, it is hard to imagine even a super algorithm for finding solutions forcing the condition P=NP to always be valid for any problem.

When reading about this prize I thought of the following nerd joke solution (probably only funny to the most nerdy of nerds....):

P=NP iff (N == 1 or P == 0), otherwise P != NP

The following math joke is hosted in many locations on the internet. I thought it would go well with the nerdy joke above:


Jacob Levman