Deolalikar claims to have solved the famous P versus NP problem. Is the proof correct? Some influential researchers doubt it: Scott Aaronson is betting 200k$ of his own money against Deolalikar.

What I find most interesting is that Deolalikar did not submit the paper to a journal, as far as I know. He didn’t even post it on arxiv like Perelman. Yet, he is receiving much attention. His name is being tweeted several times a minute. Many of the most influential theoretical computer scientists are reacting to the paper. He is getting the best peer review possible. Most similar papers don’t get so much attention.

Why is this paper different?

  • Everyone seems to agree that the paper is well written, it has nice (color!) figures and the reference section appears up-to-date and complete.  If your result is important, communicate it well.
  • Deolalikar has published just a handful of papers in theoretical computer science, and none at the major conferences. But he has enough peer-reviewed research papers to be treated as a peer.
  • While I doubt he was hired to work on complexity theory, Deolalikar is an industry researcher at HP. Being paid to do research might make you more credible.

Further reading: Deolalikar’s publication list on DBLP, A Proof That P Is Not Equal To NP? by Lipton and P ≠ NP by Baker.

Update: Porreca has the best write-up on reactions to this paper.

Update 2: The consensus after two weeks is that the proof wrong and unfixable.

14 Comments

  1. I guess there is a 3rd point in that list:

    * Prove something worth 1M$.

    If me (in the case I fulfilled all three requirements) or some of my friends out of academia (by lack of post-doc offers, satisfying all 3 conditions!) did the same about our research, the results would be near 0.

    Ruben

    Comment by Ruben Berenguel — 9/8/2010 @ 8:18

  2. Daniel, while I completely agree with your post, I think it should be noted that Deolalikar’s paper (which is a preliminary version) reportedly “made it to the web without [his] knowledge”.

    Comment by Antonio E. Porreca — 9/8/2010 @ 8:24

  3. @Ruben

    Obviously, you are never going to get as much attention when trying to solve a lesser known problem. That’s a given.

    There is an endless stream of papers by outsiders claiming to have resolved P vs NP. Deolalikar is getting a much more favorable reception. We never hear about the other papers. I’m interested in what makes him different. Why are people finding him more credible even though they (obviously) have not read the paper fully?

    Comment by Daniel Lemire — 9/8/2010 @ 8:25

  4. @Daniel

    He is getting more credit for your 3 points. He doesn’t sound like a nut, like a lot of people sound when solving the Riemann hypotheses, for example. Once or twice I checked proofs in ArXiV for the RH, they were pretty funny reads. This sounds like a legitimate attempt from someone sounding sane.

    But I won’t prove anything worth of attention outside my field ;)

    Comment by Ruben Berenguel — 9/8/2010 @ 8:28

  5. It also helps if you introduce your proof with a spiffy one-liner. If Deolalikar’s proof is correct, then I suspect, “I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts” will enter the canon of famous mathematical one-liners, alongside “I have discovered a marvellous proof, which this margin is too small to contain.”

    Comment by Ben Babcock — 9/8/2010 @ 8:40

  6. The fact it was published in a private email is important. It’s a narrative hook, something unexpected that adds a little flavor to the story. That gives the story a hint of viral nature, as it makes people more inclined to share it.

    Additionally, it seems like the theory community has gotten pretty good at quickly invalidating most bogus proofs. Whenever a proof gets a little press someone raises their hand and points out some counterexample. While we obviously need to wait for proper time for an examination of a 100 page paper, when you get used to instantaneous rebuttal, a pause starts to feel like confirmation.

    Comment by Paul — 9/8/2010 @ 8:40

  7. I think you have missed the main points. The reason everyone is excited about this is that: some experts in the area have said that this seems to be a relatively serious work, and it is not just P vs NP, but contains ideas that people think are interesting even if the proof does not work.

    Comment by Anonymous — 9/8/2010 @ 9:09

  8. @Anonymous

    I’m not dismissive of Deolalikar’s work. Yet, there is no shortage of papers with potentially interesting ideas. His instant fame is an outlier.

    Whether he just shattered theoretical computer science, or faked it really well, is beside the point. Nobody knows at this point whether his work will hold under scrutiny.

    Comment by Daniel Lemire — 9/8/2010 @ 10:37

  9. The mathematical techniques seem interesting, somewhat plausible and heretofore unexplored, this is what enticed the experts.

    The vast majority of “amateur” proofs do not have any of these qualities.

    So even if people haven’t rigorously checked the proof, that doesn’t mean they don’t have a some idea of its quality.

    Comment by Robert — 9/8/2010 @ 13:54

  10. Einstein also had just a handful of papers :-)

    Comment by Itman — 9/8/2010 @ 14:56

  11. @Itman

    Einstein was only 26 when he published his first seminal paper. Comparatively, Deolalikar is an established scientist, with a bona fide research job, a family, and so on.

    Comment by Daniel Lemire — 9/8/2010 @ 15:39

  12. Daniel,
    And Galois made a major math discovery before he was 20. It is a good point. Yet, I am not convinced: it may be just an illustration how immature was the state of math and physics 100-200 years ago.

    Comment by Itman — 9/8/2010 @ 15:49

  13. @Itman Both Perelman and Deolalikar are in their late thirties or early forties.

    Comment by Daniel Lemire — 9/8/2010 @ 16:12

  14. Reading this list of reasons I was also struck by the very good timing of the announcement. In mid-August most academics are getting back into ‘work mode’ but not yet saddled with courses to teach; their grad students are not around (as much) – it’s really the ideal time to get them to look at something new and not just dismiss it. Had the email been sent just one month later, it might have been summarily deleted for lack of time by many of the recipients. Probably a coincidence, but history is made by such chance.

    Comment by Ken — 11/8/2010 @ 20:19

Sorry, the comment form is closed at this time.

« Blog's main page

Powered by WordPress