6 ms·

Deolalikar Responds To Issues About His P≠NP Proof

51 points by nsoonhui 16y ago

yanowitz 16y ago
Regardless of how this plays out, this needs to be at the top of Top Science Stories of 2010 lists. If it is a good proof, Top News Stories of 2010 (or whatever year it is confirmed).
- jvdh 16y ago
  If this indeed proves P!=NP then i would think it would make a bit more top lists than just Top Science Stories 2010.
  - drcode 16y ago
    I think you're overestimating the value most people place on math theorems. I doubt this story will be given more importance than "robot who can do the laundry" or some similarly "soft" science stories by the mainstream press, as important as it may be.
    - yanowitz 16y ago
      OTOH, Wiles work on Fermat's Last Theorem was major news in 1993 and 1994.
      - jacquesm 16y ago
        Ask 10 random pedestrians if they remember what the first name was of 'Wiles' and what he did. People are far more likely to remember things such as the world trade center bombing as 'major news'. I'm happy enough it rated a mention on the 1993 wikipedia page: http://en.wikipedia.org/wiki/1993 http://en.wikipedia.org/wiki/1993
amichail 16y ago
There's quite a lot of interest in the proof by some key experts despite their general impression that the proof is wrong and unfixable. Maybe experts are using this proof as an opportunity to promote theoretical computer science? It's a way to get more grad students and funding?
- vecter 16y ago
  Or, more likely, there are lots of good ideas that can be applied to other difficult problems.
  - nsoonhui 16y ago
    But this is not a sure point; the ideas may be fresh, but it's too early to tell whether it's useful for other problems in computer science.
    - ugh 16y ago
      Doesn’t really matter because if they never care to look they will never find out.
- CitizenKane 16y ago
  My impression is that while the proof may have issues that are unfixable that the approach taken in the proof is one that's novel and could still have interesting implications in the theory of computational complexity.
- _delirium 16y ago
  I think there's some meta-worry that if all attempts to prove P=NP are treated as kookery, nobody serious will dare circulate any work on it, and so nobody will actually end up proving it. So there seems to be some going out of their way to treat a serious good-faith effort with respect.
- bobbyi 16y ago
  People are interested because there is still hope that the proof is not unfixable.
robinhouston 16y ago
The sad part is that “Vinay Deolalikar is standing by his P!=NP claim and proof.” It will be harder for future attempts to be taken seriously, if even the author of this comparatively-serious effort ends behaving like a crank rather than a scientist. Edited to add: I don't mean to give the impression I'm unsympathetic to Deolalikar's predicament. He didn't intend the draft to be public as far as I know, and it's hard to back down from a public claim like this. But all the experts who have studied it believe it to be flawed; there is a wiki documenting specific problems in detail; and Terry Tao is speculating about whether it could be proven that no strategy of that general sort could possibly work. It is definitely a worrying sign for Deolalikar to be standing by his work at this point. I'm not sure whether the downvotes are because you disagree with this assessment, or simply because I didn't explain myself very clearly. If you look at any mathematical crank – and there are many, with varying levels of mathematical education – the basic story is always the same. It begins with an honest mistake made in good faith; what distinguishes the crank is refusal to learn from his or her mistakes. I hope I'm wrong, and Deolalikar sees sense and withdraws his claim at least until he's addressed the concerns that have been raised so far.
- sriramk 16y ago
  I have more sympathy. The guy has worked on this for a few years. I'd stick to my guns too (for a while atleast) :)
  - benofsky 16y ago
    He also didn't intend for it to be published!
    - shadowfox 16y ago
      I am not surprised by OP's response though. A number of people on Lipton's page, including some people with strong credentials, were of the opinion that the researchers were wasting their time.
- brg 16y ago
  There is a huge difference between being a crank and being incorrect. The death of subtly is depressing. This line by Lipton is a response to the questions that were raised when the preprint was removed Deolalikar’s personal HP page on Monday. Many were wondering if it was a retraction, and this is denying that. But as so far as I have seen in Toa's wiki or Lipton's forums, there has not yet been a specific object to any lemma or claim in the paper. The author has no more reason to believe there is a flaw in his argument than he did on August 6.

51 points by nsoonhui 16y ago

Regardless of how this plays out, this needs to be at the top of Top Science Stories of 2010 lists. If it is a good proof, Top News Stories of 2010 (or whatever year it is confirmed).

jvdh 16y ago
If this indeed proves P!=NP then i would think it would make a bit more top lists than just Top Science Stories 2010.
- drcode 16y ago
  I think you're overestimating the value most people place on math theorems. I doubt this story will be given more importance than "robot who can do the laundry" or some similarly "soft" science stories by the mainstream press, as important as it may be.
  - yanowitz 16y ago
    OTOH, Wiles work on Fermat's Last Theorem was major news in 1993 and 1994.
    - jacquesm 16y ago
      Ask 10 random pedestrians if they remember what the first name was of 'Wiles' and what he did. People are far more likely to remember things such as the world trade center bombing as 'major news'. I'm happy enough it rated a mention on the 1993 wikipedia page: http://en.wikipedia.org/wiki/1993 http://en.wikipedia.org/wiki/1993

amichail 16y ago

There's quite a lot of interest in the proof by some key experts despite their general impression that the proof is wrong and unfixable. Maybe experts are using this proof as an opportunity to promote theoretical computer science? It's a way to get more grad students and funding?

vecter 16y ago
Or, more likely, there are lots of good ideas that can be applied to other difficult problems.
- nsoonhui 16y ago
  But this is not a sure point; the ideas may be fresh, but it's too early to tell whether it's useful for other problems in computer science.
  - ugh 16y ago
    Doesn’t really matter because if they never care to look they will never find out.
CitizenKane 16y ago
My impression is that while the proof may have issues that are unfixable that the approach taken in the proof is one that's novel and could still have interesting implications in the theory of computational complexity.
_delirium 16y ago
I think there's some meta-worry that if all attempts to prove P=NP are treated as kookery, nobody serious will dare circulate any work on it, and so nobody will actually end up proving it. So there seems to be some going out of their way to treat a serious good-faith effort with respect.
bobbyi 16y ago
People are interested because there is still hope that the proof is not unfixable.

robinhouston 16y ago

The sad part is that “Vinay Deolalikar is standing by his P!=NP claim and proof.” It will be harder for future attempts to be taken seriously, if even the author of this comparatively-serious effort ends behaving like a crank rather than a scientist. Edited to add: I don't mean to give the impression I'm unsympathetic to Deolalikar's predicament. He didn't intend the draft to be public as far as I know, and it's hard to back down from a public claim like this. But all the experts who have studied it believe it to be flawed; there is a wiki documenting specific problems in detail; and Terry Tao is speculating about whether it could be proven that no strategy of that general sort could possibly work. It is definitely a worrying sign for Deolalikar to be standing by his work at this point. I'm not sure whether the downvotes are because you disagree with this assessment, or simply because I didn't explain myself very clearly. If you look at any mathematical crank – and there are many, with varying levels of mathematical education – the basic story is always the same. It begins with an honest mistake made in good faith; what distinguishes the crank is refusal to learn from his or her mistakes. I hope I'm wrong, and Deolalikar sees sense and withdraws his claim at least until he's addressed the concerns that have been raised so far.

sriramk 16y ago
I have more sympathy. The guy has worked on this for a few years. I'd stick to my guns too (for a while atleast) :)
- benofsky 16y ago
  He also didn't intend for it to be published!
  - shadowfox 16y ago
    I am not surprised by OP's response though. A number of people on Lipton's page, including some people with strong credentials, were of the opinion that the researchers were wasting their time.
brg 16y ago
There is a huge difference between being a crank and being incorrect. The death of subtly is depressing. This line by Lipton is a response to the questions that were raised when the preprint was removed Deolalikar’s personal HP page on Monday. Many were wondering if it was a retraction, and this is denying that. But as so far as I have seen in Toa's wiki or Lipton's forums, there has not yet been a specific object to any lemma or claim in the paper. The author has no more reason to believe there is a flaw in his argument than he did on August 6.