4 ms·
R.J. Lipton - A proof that P is not equal to NP
- theDoug 16y agoThis was also good the last three times today it appeared on HN. :)
- sidww2 16y agoThe reason I posted a link regarding the same topic again is because this is a link to a blog post by a respected complexity theorist which actually discusses the proof albeit cursorily.
- cgranade 16y agoIn all fairness, this is an article by someone who knows his stuff saying maybe. There's so many crackpots going after P ≠ NP that we need to hear from those people saying this time is different. The news to this article isn't that a claimed proof exists, but that R. J. Lipton is saying it seems plausible.
- sidww2 16y agoYeah - I updated the post title to make that a bit more clear.
- ilkhd2 16y ago[jokingly] Would be interesting to know, what Does Perelman think about the proof? At least it is not from math community, so probably it is ok to take the million...
- akshayubhat 16y agoScot Aaronson bets 200k$ that this proof isnt true http://scottaaronson.com/blog/?p=456 http://scottaaronson.com/blog/?p=456
- po 16y agoReading Lipton's description of this paper I think I understand how normal people feel when they listen to geeks talk about technology.
- keefe 16y agoThe paper is rather complicated, you can see it here http://www.hpl.hp.com/personal/Vinay_Deolalikar/#s.p http://www.hpl.hp.com/personal/Vinay_Deolalikar/#s.p. on the author's site. it would be nice to believe this is solved, but my gut instinct is that it will not be vetted.