The P vs. NP problem is a problem about problems. How’s that for problematic? It deals with the class of problems that are solvable by computer and, roughly speaking, it asks whether the class of problems that can be easily solved (that’s P) is the same as the class of problems whose solutions can be easily verified to be actual solutions (that’s NP). It’s suspected that P and NP are very different creatures, if only because everybody wants it to be so: if P = NP then modern cryptography, including things like internet shopping that need it, could theoretically tumble down like a house of cards. These consequences, as well as the problem’s difficulty, are part of what made P vs. NP one of the million-dollar Millennium Prize Problems.
So when Vinay Deolalikar, a researcher at Hewlitt-Packard Labs, thought he had proved that P and NP were indeed distinct, word shot ’round the mathematical community like wildfire. And that is where the story gets interesting in a different way. As happened with recent efforts to prove the Density Hales-Jewett Theorem (see the “Massively Collaborative Mathematics” entry here), an internet community of scholars instantly sprang up and began to go to work, this time on Deolalikar’s paper. Within weeks the proposed proof had been collectively received, reviewed, and dissected by top scholars, a process that in previous generations would have been a logistical nightmare and taken far longer. Unfortunately the proof came up short, although leading researchers credit Deolalikar with coming up with some interesting new ideas. The collective efforts on proving the Density Hales-Jewett Theorem and disproving Deolalikar’s approach have some social scholars believing that the internet could revolutionize research much like the printing press did millennia ago. In effect we may be entering a new research age, one where some major discoveries are “crowd-sourced” and can come at a much faster pace than before. The story was picked up by Nature, the NY Times (whose article provides the title for this post), and the London Telegraph.