On 6 August 2010, Vinay Deolalikar, a mathematician working at Hewlett-Packard Laboratories in Palo Alo, California, distributed a note to some colleagues claiming that he had solved the “P not NP” problem, a most famous and potentially far-reaching question at the nexus of mathematics and computer science. Deolalikar’s manuscript is available here: Deolalikar paper.
The Clay Mathematics Institute describes this problem as follows (Clay):
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
If Deolalikar’s solution were to stand scrutiny, he could receive a prize of US$1 million that has been offered by the Clay Mathematics Institute for the solution. Some initial response was cautiously optimistic, but now there are indications that the tide may be turning against it.
In any event, the episode has highlighted the emergence of a new mode of collaboration for research mathematics. Here is an excerpt from a commentary by John Markoff of the New York Times (see URL below):
Some of the researchers said that until now such proofs had been hashed out in colloquiums that required participants to be physically present at an appointed time. Now, with the emergence of Web-connected software programs it is possible for such collaborative undertakings to harness the brainpower of the world’s best thinkers on a continuous basis.
In his recently published book “Cognitive Surplus: Creativity and Generosity in a Connected Age” (Penguin Press), Clay Shirky, a professor of interactive telecommunications at New York University, argues that the emergence of these new collaborative tools is paving the way for a second scientific revolution in the same way the printing press created a demarcation between the age of alchemy and the age of chemistry.
“The difference between the alchemists and the chemists was that the printing press was used to coordinate peer review,” he said. “The printing press didn’t cause the scientific revolution, but it wouldn’t have been possible without it.”
Now, he says, the new tools are likely to set off a similar transformation.
“It’s not just, ‘Hey, everybody, look at this,’ ” he said, “but rather a new set of norms is emerging about what it means to do mathematics, assuming coordinated participation.”
Along this line, the following Scott Aaronism article lists “Ten Signs that a Claimed Result is Wrong,” which are good to keep in mind for any new mathematical result of this sort: Online article. See also our blog Quick tests for checking whether a new math result is plausible.
References
New York Times
New Scientist
Nature article
Richard Lipton’s blog
U.K. Telegraph