When There's $1,000,000 Involved, Your Proof Had Better Be Right

August 27, 2010

The problem—P≠NP—asks whether easy-to-solve problems (P) are the same as problems that have easy-to-check solutions (NP). It's one of the Clay Mathematics Institute’s Millennium (or $1 million) Problems.

Researchers since the 1970s have wondered about P=NP, that is, whether there's a hidden order to NP problems that makes them solvable. That could lead to universal solutions to a host of apparently intractable problems.

On August 6, 2010, Hewlett-Packard researcher Vinay Deolalikar posted a 100-page proof, claiming that NP problems cannot be solved as easily as those in the P category. He applied a type of P equation to an NP problem, and then came up with a contradiction. Thus, P≠NP.

Deolalikar’s proof created a stir in print and online.

"It's definitely an approach that we haven't seen before," said Richard Lipton (Georgia Institute of Technology) in an August 10 interview with Nature. Deolalikar's proof is "complicated and it's not clear that it's going to work. But it's certainly not clear in my mind that it's going to fail."

Lipton covered the story on his blog (here) and exchanged emails with Deolalikar. “Perhaps the biggest surprise was that a lot of people do care,” wrote Lipton in an August 15 post. “One lesson we learned is there are hundreds of thousands of people who were interested, there were hundreds of people who were willing to write thoughtful comments, and there were a number of superstar mathematicians and theorists who were willing to work hard to get to the truth of what Vinay Deolalikar claimed.”

Scott Aaronson (MIT) wrote in an August 9 post on his blog (Shtetl-Optimized), “I really, really doubt that Deolalikar’s proof will stand.” In a later post titled “Eight Signs A Claimed P≠NP Proof Is Wrong,” he wrote, “A clear consensus has emerged that the proof, as it stands, is fatally flawed.”

Michael Nielsen reacted by hosting a page on the polymath project wiki to house the public discussion and dissect Deolalikar’s work.

Leo Gomes, writing for Forbes (August 12), offered the reaction of Terence Tao: “To establish this claim, Deolalikar employs tools from (one part of math) together with some other methods "revolving around (another part.) However, while developing these tools, it appears that Deolalikar has accidentally (and incorrectly) amplified the power of these tools from something that is too weak to establish this claim, to something that is far too strong. As a consequence, he proves statements … that are too strong to really be believable.”

Gomes (Forbes, August 12) also offered the reaction of Manindra Agrawal (Indian Institute of Technology Kanpur): “Agrawal said when he first heard of the Deolalikar paper, he turned to it with excitement, hoping that P=NP had finally been summited. He quickly soured on the paper’s lack of specificity, though, and now is telling anyone who asks that Deolalikar isn’t even close.”

Gomes (in an August 17 Forbes post) said, “The initial reaction to Deolalikar’s paper was that while he might not have settled the P=NP issue, he had at least come up with new and interesting ways to think about the matter. Now, the conventional wisdom is nowhere near as generous. Deolalikar is said to have made some clumsy errors he could have avoided if he has spend some time with a few specialists, the way people used to do before the Web and its allure of quick fame.”

In an August 17 interview with Mint, Agrawal himself said, “it’s a bit unfortunate that the paper has been made public without the author working out all the details.”

Deolalikar has since removed the “Proof” from his website.

For more, see the Math in the News item "Gödel Prize Highlights 'P vs. NP' Problem.”

Additional Coverage: The New York Times, Telegraph, New Scientist, Nature, The Globe and Mail.