A few days ago, Vinay Deolalikar, a Principal Research Scientist at HP Labs, began circulating a draft of a paper entitled “P ≠ NP”. The mathematics and computer science communities immediately erupted in a frenzy of excitement and activity.

The million dollar question: why the excitement? Well, that’s exactly it: it is a million-dollar question. The P vs NP problem is one of the seven Millenium Prize Problems established in 2000 by the Clay Mathematics Institute; each problem carries with it a prize of $1,000,000. One of the seven — the Poincaré Conjecture — has already been solved, by the Russian mathematician Grigori Perelman (who famously refused to accept both a Fields Medal and the $1 million). And it’s not even really about the $1 million prize; the P vs NP problem is widely agreed to be the most significant (and difficult) open question in theoretical computer science, so for someone to solve it would be a Really Big Deal.

So, did Deolalikar really solve it? Will he win the $1 million? Well… it’s way too early to tell! Here are a few things to keep in mind:

• Since P vs NP is such a famous problem, there are tons of “attempts” at solving it published all the time. Most are by people who either have an overinflated estimate of their mathematical understanding, or believe the solution was told to them in a dream by benevolent aliens, or both. Hence they aren’t even really worth serious mathematicians’ time to read. Sad but true. But this is clearly not the case here: Deolalikar is a respected researcher who has done related work in the past, and his 100-page paper is well-written and demonstrates a good understanding of the relevant issues (you don’t have to take my word for it). Even if the proof ends up having some sort of fatal flaw, it’s clear that he has some interesting new ideas that may lead to other discoveries. Hence the excitement.
• Unfortunately, there have already been some possible flaws pointed out. But keep in mind that any paper of this magnitude is bound to contain tons of errors, omissions, and typos (if you don’t believe me, try writing one sometime!). Only time will tell whether these flaws turn out to be fatal problems that invalidate Deolalikar’s entire approach, mistakes that can be fixed relatively easily, or just misunderstandings on the part of the people who pointed them out.
• Supposing the flaws are fixable and Deolalikar’s proof ends up being accepted by the mathematical community, it will still be quite a few years before he could possibly win the $1 million. First, the proof needs to be published in a major mathematical journal (which will probably take at least a year), then there is a mandatory two-year waiting period, and then a special committee has to examine the proof and decide whether to award the prize! So don’t hold your breath.

At this point, you may also be wondering what the heck the P vs NP problem actually is, and why it is so important. Fortunately, it’s the one Millenium Prize problem that I am actually qualified to explain, and in the following post or two I intend to do just that! (Unfortunately I am emphatically not qualified to explain anything about Deolalikar’s attempted proof.) I’ve been intending for quite a while to write about some interesting topics in the intersection of mathematics and computer science (my day job, after all, is as a computer scientist!) and this will provide the perfect excuse.