~~I~~n August 2010,
Vinay Deolalikar, a researcher at HP Labs, Palo Alto, e-mailed a 100-page
manuscript titled “P ≠ NP” to 22 leading computer science and mathematics
researchers. The manuscript was quickly forwarded to other researchers around
the world, with many of them dropping everything else to pore over it. It
claimed to have resolved the most high-profile open question in computer
science, a problem known simply as “P vs. NP”.

As one of the seven Millennium Prize Problems established by the Clay Mathematical Institute to encourage work on “the deepest, most difficult problems” and “important classic questions that have resisted solution for many years”, a correct resolution brought with it a $1,000,000 prize and considerable glory.

Deolalikar’s announcement came as a surprise to researchers in the area. He was not part of the community of researchers, mostly in universities across the United States and Europe, who were known to be working on the problem. His approach too was new, and unrelated to any of the approaches generally recognised as having promise in attacking the P vs. NP question. His manuscript combined ideas from such widely disparate areas of research that it was unlikely there was any one person in the world with enough insight in all those areas to be able to evaluate it offhand.

In the normal course
the manuscript would be submitted to a scientific journal, where a panel of
researchers would be assembled to perform a peer review, a process that could
take months or, on some occasions, years. But in this case, the significance of
the problem and the excitement around the manuscript spurred the community into
action. Available to them was a mature Internet with a variety of tools to
facilitate communication and collaboration. And among them was a critical mass
of younger researchers who were at home on the Internet. Over the next week,
researchers from across the world came together through blogs, Twitter and a
wiki to try and understand Deolalikar’s work. The intensity and scale of this
engagement was unprecedented, with the work of months being accomplished in a
few days.

At the heart of the matter were, of course, the problem and its solution. But
the days following Deolalikar’s announcement also brought attention to other
aspects around science: the process of vetting scientific work, the role of the
media in interpreting science for the layperson, the sometimes idiosyncratic
motivations that drive individual researchers and the changing nature of
scientific research in the age of the Internet.

*It is characteristic of all deep human problems that they are not to be approached without some humour and some bewilderment.*

*– Freeman Dyson*

~~T~~he P vs. NP question
is really a meta-problem, a problem about problems. Think of a problem found in
the daily newspaper—the Sudoku puzzle. The hardest Sudokus can take hours or
days to finish, or elude solution altogether, but once a Sudoku is solved we
can quickly verify that it has been filled in correctly. Anyone who knows the
rules of the puzzle could do it in a minute, and any solved Sudoku—no matter
how long it took to solve—can be verified equally quickly.

Computer scientists have found it convenient to classify problems roughly along these lines: how long a problem takes to solve, and how long it takes to verify the solution. (But their notions of what it means for a problem to be “hard” or to be solved “quickly” are defined in terms of the number of steps taken by an algorithm as the problem size increases.

So, while a computer algorithm may solve a standard 9x9 Suduko in a fraction of a second, it may find itself struggling as the grid grows larger in size.)

In this scheme, P and NP are two classes of problems. A problem whose solution can be verified quickly is said to be in NP. A problem that can itself be solved quickly is said to be in P. The P vs. NP question is about the relationship between these two classes of problems. It asks: if the solution to a problem can be quickly verified, does it also mean that the problem can be quickly solved? That is: is P = NP?

To see why this is a significant question, we must turn to the hardest problems in NP. These turn out to share the characteristics of Sudoku—their solutions can be easily verified, but we know of no quick and reliable way to actually solve them. As these problems grow in size, the algorithms for solving them take inordinately long on even the fastest computers we have.

The problem has been studied since as the “Travelling Salesman Problem”: given a number of cities and the distances between every pair of cities, what is the shortest tour that includes every city? The problem is a commonly occurring one at different scales: the bus that must pick up children from all over a city in time for school; the backpacker who must come up with a multi-city flight itinerary within a fixed budget.

These are termed “NP-complete” problems. It turns out that a large number of problems we are interested in solving are NP-complete. One such problem is mentioned in a German manual from 1832 titled: “The Travelling Salesman— How he should be and what he must do to obtain Orders and be sure of a happy Success in his Business—by an old Travelling Salesman.” Among other things, it advises salesmen that much time can be saved by planning travel routes carefully, and gives five well-planned tours through Germany, one covering as many as 45 destinations.

The problem has been studied since as the “Travelling Salesman Problem”: given a number of cities and the distances between every pair of cities, what is the shortest tour that includes every city? The problem is a commonly occurring one at different scales: the bus that must pick up children from all over a city in time for school; the backpacker who must come up with a multi-city flight itinerary within a fixed budget.

It can be seen even at microscopic levels. Biologists trying to understand the causes of diseases such as cancer and Alzheimer’s by modelling protein folding—the process by which a protein acquires its three-dimensional functional structure—have found that protein folding can be mapped to the Travelling Salesman Problem. Engineers who design electronic chips try to maximise the number of components on a tiny chip while minimising delay in its circuits. This requires that the length of connections between components on the chip be kept to a minimum, often requiring the computation of a salesman’s tour covering tens of thousands of cities.

~~T~~he Travelling Salesman Problem is only one among thousands of NP-complete
problems that have been identified. Every branch of engineering, science and
mathematics routinely throws up such problems. Relatively common tasks, such as
drawing schedules and timetables, deciding locations for shared amenities, packing
cargo efficiently, and minimising material wastage in industries, all present
themselves as NP-complete problems.

Since optimal solutions may be hard to achieve in reasonable time while solving these problems, we usually end up using guess-work, or we settle for an approximate solution.

Computer scientists have an affinity for colourfully named problems: the “Art Gallery problem” asks what is the fewest number of guards required to keep an eye over every part of an art gallery that is shaped a certain way; the “Piano Mover’s problem” deals with breaking down a complex navigation into smaller steps; the “Taxicab Rip-off” problem expresses the anxiety of the taxi driver who wishes to take a tourist to her destination by the longest possible route without arousing suspicion by repeating locations. But when these problems are studied, they are expressed as precise mathematical formulations.

There is apparently nothing in common between moving a piano and solving a Sudoku, but abstracted from their real-world settings, it turns out that one NP-complete problem can quickly be transformed into another NP-complete problem. This means that all NP-complete problems are—in a sense—the same problem.

Being able to solve one NP-complete problem quickly means that we can solve any NP-complete problem quickly. Since these are the hardest problems in NP, being able to do that would also mean that all of NP is really the same as P. That is, P = NP. No one (so far) has actually been able to do this, but it remains a tantalising possibility—that some bright commuter will come up with a reliable short-cut that works for all sizes of the Sudoku puzzle, and at one stroke solve thousands of the most significant and challenging computational problems known to us.

~~T~~he effect on our world would be sensational. Enormous scientific breakthroughs
would quickly follow. Our understanding of diseases such as cancer, AIDS and
Alzheimer’s would be immensely enhanced, possibly leading to their prevention
or cure. Our ability to forecast weather and natural phenomena such as
earthquakes and tsunamis would be vastly improved.

From factories to traffic to aircraft scheduling, processes would become more efficient. Large quantities of fuel would be saved. And these are only the more humdrum consequences. We may also be able to start attributing computers with thus-far human-only qualities of creativity and imagination.

Stephen Cook, who first formulated the P vs. NP question in 1971, wrote the official description of P vs. NP for the Clay Mathematics Institute. He speculated that “a practical algorithm for solving an NP-complete problem [. . .] would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of reasonable length...” Example theorems, he wrote, may include all the Clay Millennium Prize problems.

But most computer scientists and mathematicians believe that P≠NP. If they are right, partial or approximate solutions are the best we can hope to find in reasonable time when it comes to hard problems. Almost all online cryptography works by assuming that P≠NP.

This means that the security of almost every online transaction and credit card swipe rests on an unproven assumption. Proving P≠NP would soothe the apprehension that many systems that are secure today might suddenly become vulnerable.

Besides practical applications, the relationship between P and NP is a profound question whose resolution has eluded mathematicians for over half a century. Proving their relationship either way would generate deep philosophical insights into the nature of the problems that taunt us, and their solutions.

Researchers in the area—they are called complexity theorists—are usually wary of considering claims about the P vs. NP question. The question is high profile, and the fact that at least the problem statement is comprehensible without much formal training, ensure a regular stream of attempted proofs.

Researchers in the area—they are called complexity theorists—are usually wary of considering claims about the P vs. NP question. The question is high profile, and the fact that at least the problem statement is comprehensible without much formal training, ensure a regular stream of attempted proofs.

Judging by Internet discussion boards on complexity theory, it seems a popular pastime to prove P=NP by coming up with a quick method to solve one of the many NP-complete problems. These claims are inevitably disposed of, usually by providing an instance of the problem that this new method cannot solve. These message boards also have their share of P vs. NP eccentrics—those who insist they have proved a result or paradox about P vs. NP, but using methods so mind-bendingly outrageous that no one else can possibly begin to comprehend it.

Gerhard J Woeginger of the Eindhoven University of Technology maintains a “P-versus-NP” web-page on which he lists claims about the resolution of “P vs. NP”. As of March 2012, the page listed 88 claims from across the world, some proving P = NP, some proving P ≠ NP, and some proving that the matter was unprovable. None of these have gained acceptance among the research community. However, the work on P vs. NP has not all been in vain: there exists a body of serious work that rules out certain approaches and identifies promising approaches to resolving the question.

*We portray peer review to the public as a quasi-sacred process that helps to make science our most objective truth teller. But we know that the system of peer review is biased, unjust, unaccountable, incomplete, easily fixed, often insulting, usually ignorant, occasionally foolish, and frequently wrong.*

*– Richard Horton, Editor,*The Lancet

~~V~~inay Deolalikar’s
email with the manuscript titled P≠NP was sent to researchers working in the
area on August 6. The news made its first public appearance the next day on the
blog of Greg Baker, a faculty member in the Computer Science department at
Simon Fraser University. Baker reproduced Deolalikar’s email announcing his
proof, which he said he had received “a couple of steps removed”. A day later
Baker’s blog post was linked from Slashdot along with a link to the paper
itself. (Slashdot is a massively popular news and discussion website with the
tagline, “News for Nerds. Stuff that Matters.” A website linked from there will
occasionally see a surge in traffic so overwhelming that its servers crash, a
phenomenon called “slashdotting”.)

This effectively made Deolalikar’s paper public, announcing it to anyone interested, including journalists all over the world. On the same day, August 8, Richard Lipton, professor of Computer Science at Georgia Tech and co-author of a blog named “Gödel’s Last Letter and P = NP”, made a post titled “A Proof that P is not equal to NP?” He outlined Deolalikar’s proof strategy and speculated, “perhaps this is the solution we have all been waiting for”.

One of the reasons the P vs. NP question is considered challenging to resolve is that it involves dealing not with specific problems but with entire classes of problems. Deolalikar had built on previous work that allowed him to translate the classes of P and NP into specific languages in logic, and he combined this with intricate results about the structure and properties of those languages.

Very broadly, his was what is known as a “proof by contradiction”. Deolalikar was taking a problem that was known to be in NP, but assuming it to be in P, and showing that the assumption led to conclusions that were known to be false. This showed that P and NP had to be separate. The manuscript combined elements from widely disparate areas. To quote from its abstract: “We utilise and expand upon ideas from several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics.”

The validity of new scientific research is established by peer review. Typically, a paper is submitted to a journal for publication, and a small panel of reviewers, usually other researchers in the area, evaluates the contributions and correctness of the paper. The process in its most rigorous form is “double blind”: the authors of the paper and the reviewers are unaware of each other’s identities and affiliations. (At least in theory. In practice, the number of people practising specialised research in an area is often small enough for bitter or vengeful guesses to be made.)

Comments, clarifications, and suggested revisions go back and forth between reviewers and authors through an editor, and it can take months, sometimes years, before a paper is accepted or rejected by a journal.

Researchers have been submitting their findings to journals for a while now. The oldest scientific journal is generally considered to be the Philosophical Transactions of the Royal Society, established in 1665, and even then, it had a primitive version of peer review. Yet it was only in the second half of the twentieth century that peer review emerged as the dominant means of vetting scientific research. The number of peer reviewed publications to a researcher’s name, and the quality of the journals they are published in have become crucial today when it comes to obtaining a PhD, a job, a promotion, or research funding, a state of affairs handily summarised in academia as “publish or perish”.

While the system of scholarly peer review has been valuable in upholding standards and ensuring correctness, it has also come in for growing criticism for being time-consuming and not always effective at keeping sub-standard work from being published. It is also seen as favouring competent, predictable work over more challenging ideas.

One survey of Nobel laureates in physics, chemistry, and medicine or physiology found that 36 papers describing work that went on to win their authors a Nobel prize were initially rejected by journals. An example often given by critics of scholarly peer review is that of Einstein’s annus mirabilis, 1905, a year in which he revolutionized physics.

In March, the relatively unknown examiner at the patent office in Bern, Switzerland, sent the German journal Annalen der Physik a paper suggesting that light rays consisted of discrete packets of energy, and that the amount of energy depended not on the intensity of light, but on its frequency. This work on the photoelectric effect earned him a Nobel prize in 1921.

In May he sent the same journal a paper with equations describing the jiggling motion of small particles in liquids, and extended this work to provide what amounted to the first real demonstration that atoms existed.

In June, he sent in a
paper that described what is now known as the special theory of relativity: if
the speed of light is constant regardless of whether its source is moving, then
space and time can only be measured relatively. In September he sent what he
termed “a very interesting conclusion” that followed from his previous paper:
an equation for the energy contained in matter: E=mc^{2}.

All four papers were published the same year after being read only by two editors of the journal (though they could be considered peers, being physicists themselves). Given that several leading scientists of the day refused to accept Einstein’s ideas even after they appeared in print, it is debatable if Einstein’s annus mirabilis would still have been one if he’d had to parry reviewers’ scepticism and helpful suggestions to include more references. (The special relativity paper famously does not contain a single reference to any other publication.)

Deolalikar’s manuscript, with its eclectic approach, would in the usual course be particularly challenging and time-consuming to evaluate through the traditional peer-review process. But something unprecedented happened in this case.

Deolalikar’s credentials as a mathematician ensured that his proof claim for P vs. NP was taken seriously by researchers. Deolalikar has a master’s degree from IIT Bombay, and a PhD in Electrical Engineering and Mathematics from the University of Southern California. He works with a reputed research lab and has a track record of published research, some of it in complexity theory.

His manuscript showed evident familiarity with related work. In addition, many of the forwarded versions of Deolalikar’s e-mail had an endorsement of sorts from Stephen Cook, who first formulated the P vs. NP question: “This appears to be a relatively serious claim to have solved P vs. NP.” These bona fides created an excitement around Deolalikar’s manuscript that was in sharp contrast to the usual scepticism reserved for P vs. NP proof claims. This excitement, combined with the research community’s presence on the Internet, sparked off a frenzied online version of peer review in which practically anyone on the Internet who could intelligently discuss the matter was a reviewer.

It began on August 9 when Suresh Venkatasubramanian, a researcher at the University of Utah, made a post to his blog titled “On the Deolalikar proof: Crowdsourcing the discussion?” He set up a shared document on Google Docs to track discussions about the manuscript. Subsequently, a wiki was set up on the website of the Polymath project, an online experiment in collaborative research, to collate news and technical analysis of the proof.

Discussions continued on Lipton’s blog, with over a thousand comments posted in a week. Involved were some of the researchers whose work Deolalikar was building upon in his proof, and a distinguished array of computer scientists and mathematicians, including two recipients of the Fields medal, considered the highest recognition that can be conferred upon a mathematician. There can be little doubt that Deolalikar’s paper had quickly conjured up for itself what was perhaps the most formidable peer review panel ever.

Some researchers were sceptical about Deolalikar’s claim from the outset. Scott Aaronson, a complexity theorist at MIT, was on vacation when Deolalikar’s paper started to make the rounds. He made a blog post on August 9 stating that while the manuscript looked interesting and competent, he had an announcement that would back up his hunch without his having to study the manuscript or be unfair to Deolalikar: “If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof of P≠ NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000.” Others were less flamboyant about their reservations.

At this stage, most people reviewing the manuscript were looking to understand it and perhaps even help Deolalikar with any gaps or flaws in his proof. It is not uncommon for complex mathematical proofs to have mistakes when they are submitted for scrutiny.

(The most famous recent example of this is perhaps Andrew Wiles’ 1993 proof of Fermat’s Last Theorem, a proof that came three and a half centuries after the conjecture. A serious gap in the proof was uncovered during peer review, and it took Wiles a year’s work, with a colleague’s help, to address it.)

The crowd-sourced review of Deolalikar’s manuscript quickly began to uncover typos and minor errors, as well as larger issues that needed clarification. Deolalikar uploaded to his website three drafts of the manuscript in the first five days of its public existence.

One gap in the proof was communicated via Twitter by Ryan Williams, then a postdoctoral fellow at IBM Almaden, in a series of five tweets beginning: “This P vs. NP claim is getting tons of press. I am really doubtful that it works. Hard to convey my scepticism in a tweet, but here goes...” Some of the researchers whose work Deolalikar had built upon had themselves uncovered flaws in the way their work was being used.

Neil Immerman, whose work Deolalikar had relied upon for an important step in his proof, wrote an email to Deolalikar, also published on Lipton’s blog, that pointed out a “serious hole” in the way his work was used. Ronald Fagin, the founder of descriptive complexity theory, pointed out a counter-example that questioned another of Deolalikar’s steps. The list of issues mounted on Lipton’s blog and the community wiki.

Terence Tao, a
mathematician from UCLA and a Fields Medallist, was one of the most active
online reviewers of Deolalikar’s manuscript. He wrote, “I think there are
several levels to the basic question ‘Is the proof correct?’:

- Does Deolalikar’s proof, after only minor changes, give a proof that P≠NP?
- Does Deolalikar’s proof, after major changes, give a proof that P≠NP?
- Does the general proof strategy of Deolalikar... have any hope at all of
establishing... complexity separation results?”

On August 13, exactly a week after the manuscript was sent out, the consensus of the research community, as expressed by Tao, was that the answer to the first two questions was a “definite no”, and to the third, “probably not”.

*Science stories usually fall into three families: wacky stories, scare stories and “breakthrough” stories.*

*– Ben Goldacre*

~~E~~ven as Deolalikar's
proof claim was starting to flounder, the print media in India had picked the
story off the Internet. Most national newspapers carried the news prominently
with headlines highlighting the Indian connection: “Indian scientist offers
proof for P=NP riddle” (*Mint*, August 11); “World’s toughest sum cracked, says
Indian-origin geek” (*Times of India*, August 12); “NRI cracks toughest maths
riddle” (*The* *Indian Express*, August 12); “Indian scientist proposes solution to
math problem” (*The Hindu, *August 12). The BBC website reported it under the
title, “Million dollar maths puzzle sparks row” (August 11), a far more
accurate representation of the proof's status at the time.

The last time an Indian scientist claimed a similarly sensational result, it was in the same area of research. In 2002, Manindra Agrawal, currently N Rama Rao Chair Professor in the Department of Computer Science and Engineering, IIT Kanpur, was the lead author of a paper titled “PRIMES is in P”. The paper gave a quick, general and elegant algorithm for determining whether a number was prime or not, something that had proved elusive for a couple of thousand years.

Despite the paper being celebrated by the research community almost
immediately, the media response in India was slow. “The media was not so
aggressive at the time,” Agrawal recounts over the phone. He recalls that the
first media report of the work done in Kanpur appeared in *The New York Times*,
and subsequently, *The Times of India* carried the news on its International
page. Agrawal and his co-authors went on receive the prestigious Gödel Prize
and the Fulkerson Prize for their work.

The fact that
Deolalikar’s proof had run into problems went largely unreported in the Indian
media. An exception was *Mint*, which on August 17 carried an article titled “P =
NP: the claim, the hype and the mini-furore” that linked the episode with an
Indian tendency to overstate achievements in science and technology. The
article was written by sci-tech journalist Seema Singh, who worked for *Mint* at
the time and now writes for Forbes India. She says, “The first story was
written by a features writer and I thought it was a bit one-sided. So I
immediately told my editor I wanted to do a rebuttal.”

According to Singh, a follow-up science story is relatively rare in the Indian press. “Editors are not interested in science unless it’s a blockbuster story. They believe there’s no readership.” Besides, science stories from India tend to be hard to come by because research institutions don’t keep the media informed about their work.

Singh says, “Every professor I meet complains about not getting good students. But how will you get good students if you don’t communicate your work and get young people excited?” All this, Singh says, contributes to a climate in which reporting about science is increasingly hard: “Today there are perhaps only a dozen dedicated science journalists in a country of 1.2 billion. I must say I’m quite disillusioned with the whole system.”

*There is more religion in men’s science than there is science in their religion.*

*– Henry David Thoreau*

~~A.~~ K. Ramanujan’s
essay “Is There an Indian Way of Thinking” was inspired by and dedicated to his
father, who was without any sign of conflict a mathematician and astronomer as
well as an expert astrologer.

In the essay, Ramanujan suggests that there indeed is an Indian way of thinking: one which is capable of operating from independent, and apparently irreconcilable, world-views as required by the context.

He writes, “When Indians learn, quite expertly, modern science, business, or technology, they ‘compartmentalise’ these interests; the new ways of thought and behaviour do not replace, but live along with older ‘religious’ ways.”

This view appears to be borne out in the world of Indian science. An institutional embodiment of Ramanujan's father might well be the Indian Space Research Organisation (ISRO), known to schedule launches on auspicious dates, and to take scale-models of spacecraft to Tirupati to seek Lord Venkateswara’s blessings.

A survey conducted in 2007-08 by the Institute for the Study of Secularism in Society and Culture along with the Centre for Inquiry India asked 1,100 scientists from 130 Indian institutions questions about their world-views.

The results showed that 49 per cent believed prayer was effective; 38 per cent believed god performs miracles; 24 per cent believed holy people could perform miracles; and 41 per cent approved of the practice of having satellites and rockets blessed before they were launched. These were scientists who were—to use Ramanujan’s phrase—quite expert: the largest number of respondents were from four of the IITs and the Indian Institute of Science.

The work in Deolalikar’s manuscript may have been done in the United States, but its personal significance to him appeared to lie in the cultural context of being Indian and Hindu.

The last paragraph of the email announcing the proof mentions that the effort was a purely individual one: “This work was pursued independently of my duties as a HP Labs researcher, and without the knowledge of others. I made several unsuccessful attempts these past two years trying other combinations of ideas before I began this work.”

In the days after the manuscript was released, the biography on his official website read: “Born in 1971 in New Delhi, India. Married with two children. Other interests include historical and religious aspects of Hindu Dharma. Indian citizen.”

The manuscript itself began with the verse from the Bhagavad Gita proclaiming man’s right to action but not its fruit. Deolalikar dedicated the work to his late parents and his aunt “for all their hard work in raising me”, and to his grandparents for “their struggle to educate my father in spite of extreme poverty.”

He termed the work part of his “Matru-Pitru Rin.” It was footnoted as “the debt to mother and father that a pious Hindu regards as his obligation to repay in this life.”

One of the issues the community at large had with Deolalikar’s manuscript was its apparent lack of rigour. Those trying to understand the manuscript often reported frustration at terms not being precisely defined.

Usually, large mathematical proofs are divided into proofs of smaller results, a structure that allow specific claims to be examined, but Deolalikar’s manuscript did not follow the convention, making it hard to fathom.

Some of those studying the manuscript accused him of “hand-waving”. Others were more sympathetic, seeing that Deolalikar’s original email stated that the paper was only meant to “provide an understanding of the global framework of the proof”, and that “technical and computational details within chapters were minimised as much as possible”.

But the tone of the email suggested he was convinced he had a proof, even if he wasn’t sharing all the details. The subject line was authoritative: “Proof announcement: P is not equal to NP”.

It began, “I am pleased to announce a proof that P is not equal to NP…” and went on to thank the “many esteemed researchers” whose work he had built upon. This was unusual given that mathematicians tend to be remarkably cautious about claiming breakthrough results.

Prof Manindra Agrawal, who had a long email exchange with Deolalikar, says he communicated a serious flaw in the manuscript after which he stopped responding. Agrawal says, “I don’t believe that this will work at all. Not even as an approach.”

A commenter on Lipton’s blog who went by the handle “vloodin” and had made particularly insightful technical comments during the discussions, speculated about Deolalikar's motives:

“The real question is why would someone who clearly has enough background to understand relevant material (and hence not a complete quack) do something like this, and how can he save face given this embarrassment. Another question is was he aware that his proof is wrong or incomplete when he e-mailed it out.

“My guess is that he did not think [the] proof strategy is so wrong, but probably was aware that [the] proof was incomplete. Perhaps he thought that details can be fixed, and his vague ideas (here we have more a sketch or a strategy) can be made precise.”

Another anonymous commenter speculated that Deolalikar had made his work public in haste so as to be eligible for a Fields Medal. The medal is awarded every four years at the International Congress of Mathematicians (ICM) to up to four mathematicians under 40. Deolalikar was 39 at the time, and his proof claim appeared two weeks before ICM 2010 was to be held for the first time in India.

On August 17 2010, Deolalikar removed all drafts of the paper from his website and posted an announcement saying he had fixed the issues raised and submitted the revised manuscript to a journal. Contacted by email in October 2010, he did not wish to comment in order to “maintain the integrity of the review process of the (considerably expanded) manuscript.”

He said he had been reflecting on the media attention and the unique peer review his work had received, and he believed they raised important questions, but he did not want to comment till his revised manuscript had been reviewed.

He hinted that his views may be perceived as idiosyncratic. “I am a devout practising Hindu,” he wrote. “Therefore some of my perspectives may be difficult to understand for someone who is not.”

*I have always prepared and made my experiments with my own hands, working and thinking at the same time. I do not think I could work in company, or think aloud, or explain my thoughts at the time.*

*- Michael Faraday*

~~T~~he research community
made up its mind about Deolalikar’s original proof attempt in about a week.
Deolalikar says his revised manuscript is still under review at a journal as of
April 2012, 20 months after it was submitted, a difference in timescales that
highlights the extraordinary achievement of the online peer review his
manuscript

received.

In the process, students and young researchers from across the world had a chance to see the workings of some of the finest minds in mathematics and complexity theory, and to collaborate briefly with them.

The intense media attention also appears to have raised public awareness of the P vs. NP question: the UK betting exchange website, Smarkets, shows P vs. NP as the heavy favourite to be the next Clay Millennium Prize problem to fall.

The episode also drew attention to the increasing possibilities offered by the Internet for open and collaborative research. Several online initiatives try to overcome the high cost and delay inherent in traditional journals: the Public Library of Science (PloS) runs journals with the aim of providing free access to research; open access archives, such as arXiv (pronounced “archive”) run by Cornell University, host electronic prints of papers, often while the papers are under review by journals.

The only Clay Millennium Prize problem to be solved so far had its solution—a proof of the Poincaré conjecture—uploaded on arXiv in three instalments in 2002 and 2003. The proof was provided by the Russian mathematician Grigori Perelman, who chose not to publish the work in a journal. (He also chose to turn down the Clay Prize and decline the Fields Medal).

The Polymath blog and the website Math Overflow both allow mathematicians to collaborate on solving problems. The Galaxy Zoo website uses volunteers over the Internet to help classify galaxies from telescope images. Millions of galaxies have been classified and the resulting data has generated a significant amount of research work.

There is now a social networking site for scientists and researchers–ResearchGate–with tools for online collaboration. In September 2011, a computer game called Foldit harnessed crowd-sourcing to provide a solution to an NP-complete protein folding problem in ten days. The problem, linked to AIDS research, had eluded solution for 15 years.

As to whether the Internet lives up to its promise in revolutionising the processes of science, and as to whether Deolalikar ultimately has a proof to decide P vs. NP, we will have to wait and see. As he sagely averred in an email while deferring comment: “Time gives perspective and wisdom which is not easily attainable otherwise.”