4 ms·

Fatal Flaws in Deolalikar’s P ≠ NP Proof?

34 points by bumbledraven 16y ago

guelo 16y ago
oh well, it was fun while it lasted.
- RiderOfGiraffes 16y ago
  The ride isn't over yet. This happened - in private - to Wiles many times over, but each time he had the knowledge, insight and ability to add the extra material. Then it went public, and even then there was a hole. That eventually required Taylor's assistance. Math is like this. Lots of people with tangential deep knowledge are bringing their attention to the problem, but Deolalikar likely has more that he hasn't presented yet. I'm not betting the proof is right, but it's not dead yet. Even more, there're ideas raised here yet to be explored, and who know, even if this proof doesn't do it on its own, perhaps it will form the foundation of a successful attack later. Math goes on.
  - bumbledraven 16y ago
    If even R.J. Lipton would "hesitate to draw parallels" between Wiles and Deolalikar, how much more so should we? As Terry Tao writes, the consensus at this point seems to be that Deolalikar's general proof strategy -- exploiting independence properties in random -SAT or similar structures -- does not have much hope of establishing non-trivial complexity separation result. Link to Tao's comment on Lipton's blog: http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/#comment-5223 http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deol...
    - RiderOfGiraffes 16y ago
      I agree - what I'm saying is that people in the blogosphere and twitterverse seem to flail between the extremes all too quickly, rather than letting things take their course. It feels like people are going to declare "Well, that's that, then." and move on to other things despite there still being much to mine, and potentially results still to find. Perhaps that would be a good thing. Let the experts work on it carefully, calmly and quietly without being constantly harried by the kibitzers demanding definite answers.
      - bumbledraven 16y ago
        While the non-experts did get excited early on, I haven't observed any flailing between extremes on the blogs of the computational complexity theorists I follow (R.J. Lipton and Scott Aaronson). Initially, Lipton seemed neutral, and Aaronson was skeptical. Since then, I've seen the dial on Lipton's blog move steadily towards "nothing to see here, move along". I personally agree with those who believe that the draft is too disorganized to warrant further study by experts. If the author had used the traditional definition/proof/lemma style, the problems that have been pointed out so far would have been immediately visible, rather taking the experts days to untangle. [edit: For example, John Harrison, the author of the HOL Light proof-checking system, wrote on August 10: "As far as I can tell, nobody’s quite managed to work out what exactly the statistical property of k-SAT he’s using is." http://scottaaronson.com/blog/?p=456#comment-44852 http://scottaaronson.com/blog/?p=456#comment-44852] I don't mean this as a critique of the Deolalikar himself, but I do think he sent out his draft too soon.
        RiderOfGiraffes 16y ago
        It seems to me (with no privileged information) that he suffered from sending a written copy to a selcet number who he expected would treat it in confidence, but not all of whom did. I think it's great that he had a "thought piece" written, and I think it's great that he started to consult a few trusted colleagues. I think it's a real shame that the "think piece" was leaked. If he'd taken six months to go over it in person, orally, calmly and in seclusion with a few chosen colleagues then there may have been a chance to either declare it unworkable, or to fix the holes. As it is, that didn't happen and we get this mess. On the other hand, lots of people have seen - in some sense - real math in action. Maybe that's a good thing.
svag 16y ago
Just for fun, check this video about Hitler and P vs NP problems... http://www.youtube.com/watch?v=GSIodz9GWxc http://www.youtube.com/watch?v=GSIodz9GWxc

34 points by bumbledraven 16y ago

guelo 16y ago

oh well, it was fun while it lasted.

RiderOfGiraffes 16y ago
The ride isn't over yet. This happened - in private - to Wiles many times over, but each time he had the knowledge, insight and ability to add the extra material. Then it went public, and even then there was a hole. That eventually required Taylor's assistance. Math is like this. Lots of people with tangential deep knowledge are bringing their attention to the problem, but Deolalikar likely has more that he hasn't presented yet. I'm not betting the proof is right, but it's not dead yet. Even more, there're ideas raised here yet to be explored, and who know, even if this proof doesn't do it on its own, perhaps it will form the foundation of a successful attack later. Math goes on.
- bumbledraven 16y ago
  If even R.J. Lipton would "hesitate to draw parallels" between Wiles and Deolalikar, how much more so should we? As Terry Tao writes, the consensus at this point seems to be that Deolalikar's general proof strategy -- exploiting independence properties in random -SAT or similar structures -- does not have much hope of establishing non-trivial complexity separation result. Link to Tao's comment on Lipton's blog: http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/#comment-5223 http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deol...
  - RiderOfGiraffes 16y ago
    I agree - what I'm saying is that people in the blogosphere and twitterverse seem to flail between the extremes all too quickly, rather than letting things take their course. It feels like people are going to declare "Well, that's that, then." and move on to other things despite there still being much to mine, and potentially results still to find. Perhaps that would be a good thing. Let the experts work on it carefully, calmly and quietly without being constantly harried by the kibitzers demanding definite answers.
    - bumbledraven 16y ago
      While the non-experts did get excited early on, I haven't observed any flailing between extremes on the blogs of the computational complexity theorists I follow (R.J. Lipton and Scott Aaronson). Initially, Lipton seemed neutral, and Aaronson was skeptical. Since then, I've seen the dial on Lipton's blog move steadily towards "nothing to see here, move along". I personally agree with those who believe that the draft is too disorganized to warrant further study by experts. If the author had used the traditional definition/proof/lemma style, the problems that have been pointed out so far would have been immediately visible, rather taking the experts days to untangle. [edit: For example, John Harrison, the author of the HOL Light proof-checking system, wrote on August 10: "As far as I can tell, nobody’s quite managed to work out what exactly the statistical property of k-SAT he’s using is." http://scottaaronson.com/blog/?p=456#comment-44852 http://scottaaronson.com/blog/?p=456#comment-44852] I don't mean this as a critique of the Deolalikar himself, but I do think he sent out his draft too soon.
      - RiderOfGiraffes 16y ago
        It seems to me (with no privileged information) that he suffered from sending a written copy to a selcet number who he expected would treat it in confidence, but not all of whom did. I think it's great that he had a "thought piece" written, and I think it's great that he started to consult a few trusted colleagues. I think it's a real shame that the "think piece" was leaked. If he'd taken six months to go over it in person, orally, calmly and in seclusion with a few chosen colleagues then there may have been a chance to either declare it unworkable, or to fix the holes. As it is, that didn't happen and we get this mess. On the other hand, lots of people have seen - in some sense - real math in action. Maybe that's a good thing.

svag 16y ago

Just for fun, check this video about Hitler and P vs NP problems... http://www.youtube.com/watch?v=GSIodz9GWxc http://www.youtube.com/watch?v=GSIodz9GWxc