Fatal Flaws in Deolalikar’s P ≠ NP Proof? | Hacker News Reader

Fatal Flaws in Deolalikar’s P ≠ NP Proof?

rjlipton.wordpress.com

34 pointsbumbledraven7 comments

Just for fun, check this video about Hitler and P vs NP problems...

http://www.youtube.com/watch?v=GSIodz9GWxc

oh well, it was fun while it lasted.

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.

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-deol...

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.

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]

I don't mean this as a critique of the Deolalikar himself, but I do think he sent out his draft too soon.

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.

Reply on news.ycombinator.com