You may have never heard of Vinay Deolalikar, but there is a chance that he may become next year’s Turing Award winner, not to mention an overnight millionaire. It seems that Vinay dropped the news at the start of this week that he had proven that P does not equal NP. In short, this proof means that many problems we suspect are hard to solve are in fact provably hard to solve. Whether his proof succeeds or not, the Interwebs are abuzz with the news.
P versus NP is arguably the biggest unanswered problem in Computer Science, and proving it one way or another will cascade into new results and conclusions in many areas of computing and mathematics. The problem is at least 40 years old, and despite people literally devoting their entire careers to the problem, has yet to be decided. Some researchers suspect it can’t be proved, although this has not been proven either.
When a famous problem like this has been stewing for so long, it is not unusual to see sporadic cries of proof, but these need to be taken with a grain of salt. The first test is to see if the person is a flake with a proof that won’t survive a casual scan. Passing that test, the proof then has to endure the normal peer review process. Proofs that plumb difficult new ground can take years to be accepted.
It appears that Deolalikar has passed the first test - people are seriously studying his proof. However, given its complexity and length, you can expect that general acceptance will not happen overnight. More likely, specific problems will arise, challenges will be published, and Deolalikar will either respond, modify his proof, or retreat for more study. If he indeed has the golden ticket, he will be cashing a million dollar prize from the Clay Mathematics Institute sometime soon.
It’s remarkable news indeed, and perhaps the only way it would have been more remarkable would have been with a proof that P equals NP.
Feel like weighing in? Check out the proof yourself and see what you think.