17 ms·

Major (unfixable) flaw found in P!=NP paper.

104 points by amichail 16y ago

amichail 16y ago
BTW, the author has removed any mention of a proof for P!=NP from his home page: http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/
- whakojacko 16y ago
  Was it ever there? I thought he always said that the paper was done on his personal time and not related to his HP research. I read his Bio there Sunday/Monday and dont remember seeing it. Not to mention it was still being peer-reviewed when it was leaked.
  - akshayubhat 16y ago
    Yes it was there, including an official copy which he updated yesterday.
  - deleted 16y ago
    [deleted]
  - kingkilr 16y ago
    It wasn't there when the the paper first went public, however it was there this morning.
  - furtivefelon 16y ago
    It was there, mentioned that he didn't intend for it to be released so early. However, a final draft is in progress, should be done in a few days.
  - ctbarna 16y ago
    He posted something saying that it wasn't meant to be released yet. He had sent it to some experts on August 6th and it made its way into the wild on August 8th. He posted what he said was an "updated" draft. It was there this morning but is no longer.
- kvs 16y ago
  You can find revised versions at: http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/ It is being revised frequently.
phreeza 16y ago
Your title is a bit drastic, where does anyone say its unfixable in the post? edit: sorry, was viewing this from a mobile phone, which didn't skip ahead to the comment.
- kingkilr 16y ago
  It's the second word. Perhaps an edit?
- amichail 16y ago
  Charanjit Jutla says "unfixable" twice.
  - igravious 16y ago
    Yes but you've linked to a comment to the main blog post. Which is a bit untoward. A comment on a blog is hardly authoritative. I did a double-take until I realized you weren't linking to the main post. The main blog post says (and I quote) Still there remains the key question: is the proof correct? In one sense the present paper almost surely has mistakes—not just from the above objections but what one could expect of any first-draft in a breakthrough situation. The real questions are, is the proof strategy correct, and are the perceived gaps fixable? edit: the commenter Charanjit Jutla seems to know his stuff but I still maintain that an offhand comment does not warrant the definitive titling of your submission.
    - kvs 16y ago
      Do a quick search on the blogs and the names of people posting comments on it. They are authoritative sources, just because it is on a blog (run by a well known complexity theorist) doesn't mean it's less important. I am quite surprised to see so many comments from these guys and such a discussion happen in public.
      - studer 16y ago
        They don't necessarily agree with each other, though, so I'm not so sure how "authoritative" individual blog comments are (see e.g. Bradfield's followup to Jutla -- "And I don’t understand your comment about it not being known whether mu-calculus has a hierarchy of expressibility in alternation. It’s 15 years since I (and independently Lenzi) proved that it did!")
akshayubhat 16y ago
The mention of the paper has been removed from the authors homepage.
learner4life 16y ago
It is a bit sad though for the author. The author never intended the paper to be public. Now he joins the infamous list of people who published to prove P!=NP or otherwise.
- zokier 16y ago
  Well, to be fair, he didn't actually publish it. Especially not in the conventional meaning of scientific publishing.
  - nsoonhui 16y ago
    Not sure if he wanted to he could get past the conventional meaning of peer review.
- eegilbert 16y ago
  Agreed. I would be pissed at whoever publicized a draft I had sent in a private email.
- tomjen3 16y ago
  It is sad for the author, but not because he will join that list - he is not. He is going to join the much less famous list of people who attempted to prove a very difficult problem, did so in a professional way, and while they ultimately failed they did advance science. And whomever leaked that is going to end up on the shitlist of an entire community of researchers.
- joe_the_user 16y ago
  If someone seriously wants to only share their P!=NP proof privately, they need to put "not for wide circulation" as a watermark on every page. But who know what the authors thinking was? Perhaps he hoped they'd share the paper only if they were sure it was right, perhaps he expected they wouldn't share it at all. Perhaps he expected they'd share it and he was already convinced the paper was correct. Perhaps he didn't care to what people outside the field thought...
  - 16y ago
ewjordan 16y ago
Until a major chorus of experts chimes in with "Yup, this is curtains for this approach", I think it would be wise not to take too seriously any blog comments based on quick reactions to the paper. ...just as it would be unwise to take the paper itself too seriously until a chorus of experts tells us that it's looking pretty good.
- noodle 16y ago
  indeed. there are probably not many people on HN or people who are going to post comments on blogs that are qualified to actually weigh in on this type of thing.
- deleted 16y ago
  [deleted]
- akshayubhat 16y ago
  There are several indicators, the author of the comment seems to be a researcher at an IBM R&D center. Also the original author removed the paper from him web page. Thus which indicates that he is probably backing out on his claim.
  - hubb 16y ago
    removing the paper doesn't necessarily mean that at all, he probably just wants finish editing it and getting peer feedback before he releases it officially
    - studer 16y ago
      Or maybe HP legal told him he couldn't use their web server to host unpublished material...
      - barkingcat 16y ago
        It would be extremely unwise of HP to shut him down - regardless of whether his proof works out in the end, this is a significant piece of work contributed for the further understanding of hard math problems - which is what HP ideally wants to represent. To say no to endeavours like this would be to say that they have no soul and no will for the enhancement of human knowledge.
tierack 16y ago
Whatever comes of this paper specifically, it's been a very entertaining couple of days to watch this unfold.
- maqr 16y ago
  I've been watching it the whole time, and I still have absolutely no idea what's going on.
  - dschobel 16y ago
    SCIENCE!!! </zed shaw>
palish 16y ago
Could some math expert (cperciva?) read the paper, read this blog post, and tell us the results?
- cperciva 16y ago
  I've skimmed the paper, but it's way over my head. It would take me years of study to understand everything in this paper. (I'm confident that I could do so if I wanted to -- but my expertise lies in entirely different directions.)
  - palish 16y ago
    Wow. It's so strange to realize how incredibly massive the field of mathematics is. As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. (Edit: of course, now I regret writing this. What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures.) But to know that it would take someone as insanely experienced as cpervica years of study to understand that proof... Wow.
    - pmjordan 16y ago
      As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. That's quite a bold claim.
      - palish 16y ago
        At this point, I have >10 years of programming experience. I've been programming for the majority of my childhood and the entirety of my adult life. I don't like to overestimate my own abilities, and I wish I could prove to you that my above claim is true. I simply have enough experience where I know for a fact that I can understand 99% of algorithms and architectures that were designed to solve a practical real-world problem. So you're right, "there isn't a single..." is probably pushing it. But I'd definitely stand by the fact that I can read, understand, and re-implement 99% of algorithms or architectures. My point is simply that the breadth of the field of software engineering apparently pales in comparison to that of mathematics. Or rather --- it's very strange to me that if you are an expert in a given branch of mathematics, then all of your lifetime of experiences cannot be applied to an entirely different branch. If I understand cperciva correctly, if you want to learn a particular specialized branch of mathematics, then you basically have to start from the ground-up (years). It would basically be equivalent to wiping your memory of all programming knowledge, then re-learning it all, in terms of effort. It's just strange / interesting that mathematics works that way.
gojomo 16y ago
P≠NPin' ain't easy.
- kenjackson 16y ago
  Anything goes when it comes to FOs, because ...
- jberryman 16y ago
  How long have you been waiting to write that?
- kevinherron 16y ago
  You seriously just made my day.
- jasonwatkinspdx 16y ago
  I normally don't vote up humor here because I like the snr, but this got me. Well played sir.
- dunstad 16y ago
  I'm afraid I've missed something here. Anyone care to provide an explanation?
  - martincmartin 16y ago
    "Pimpin' ain't easy"
  - deleted 16y ago
    [deleted]
troutwine 16y ago
Clearly I need to study more.
deleted 16y ago
[deleted]
jmatt 16y ago
All these academics that lay low then pop up with problems and call Deolalikar's contribution unfixable infuriate me. They bring out the worst in the same way that bad QA employees do. They create no wealth and add little value. They slow down and confuse the process. But in the end they are still necessary. There is something to be said about how one reports such problems. Most here know a great QA person that reports relevant problems in a intelligent manner and is there to help find solutions. Versus the QA person that just cranks out an endless stream of wonky insane problems. All make you look bad and all are difficult to reproduce, understand or address. It's my understanding that his approach is a radical and new way to attempt to solve the P!=NP problem. So it's no surprise that at first glance the vast majority of average math and computer scientists would think it was not a valid approach. And, again no surprise to me, that has ended up to be the case. I don't pretend to understand this flaw or Deolalikar's paper. But I do understand the type of person that posts comments like that... It looks like the math community has settle on a wiki to unofficially collect news and information on the paper: http://michaelnielsen.org/polymath1/index.php?title=Deolalikars_P!%3DNP_paper http://michaelnielsen.org/polymath1/index.php?title=Deolalik...
- brent 16y ago
  The claim is that the proof is unfixable. Proofs are either right or wrong. Good academics are supposed to checks proofs of their colleagues. There is no claim as to the merit of contributions made by Deolalikar. So, why exactly do these academics infuriate you?
  - jmatt 16y ago
    So, why exactly do these academics infuriate you? I'm quite clear if you read more than one sentence. It's the way this guy responded to a comment of a blog about the paper. It just seems like a bad place to post a real unfixable flaw to the paper. Assuming the commenter is right (also possibly a bad assumption) why not put some effort into your response that will be read by every computer science and math person you'll ever work with in the future. For instance how does one respond, follow up, contact this guy? I have to go google him wtf. It's the equivalent to nitpicking. In the end someone else will have to pick up the pieces of what he said and analyze it and rewrite it and repost it. So to me he seems like the guy from QA that no one wants to work with - a bad team player.

104 points by amichail 16y ago

BTW, the author has removed any mention of a proof for P!=NP from his home page: http://www.hpl.hp.com/personal/Vinay_Deolalikar/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/

whakojacko 16y ago
Was it ever there? I thought he always said that the paper was done on his personal time and not related to his HP research. I read his Bio there Sunday/Monday and dont remember seeing it. Not to mention it was still being peer-reviewed when it was leaked.
- akshayubhat 16y ago
  Yes it was there, including an official copy which he updated yesterday.
- deleted 16y ago
  [deleted]
- kingkilr 16y ago
  It wasn't there when the the paper first went public, however it was there this morning.
- furtivefelon 16y ago
  It was there, mentioned that he didn't intend for it to be released so early. However, a final draft is in progress, should be done in a few days.
- ctbarna 16y ago
  He posted something saying that it wasn't meant to be released yet. He had sent it to some experts on August 6th and it made its way into the wild on August 8th. He posted what he said was an "updated" draft. It was there this morning but is no longer.
kvs 16y ago
You can find revised versions at: http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/ http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/ It is being revised frequently.

phreeza 16y ago

Your title is a bit drastic, where does anyone say its unfixable in the post? edit: sorry, was viewing this from a mobile phone, which didn't skip ahead to the comment.

kingkilr 16y ago
It's the second word. Perhaps an edit?
amichail 16y ago
Charanjit Jutla says "unfixable" twice.
- igravious 16y ago
  Yes but you've linked to a comment to the main blog post. Which is a bit untoward. A comment on a blog is hardly authoritative. I did a double-take until I realized you weren't linking to the main post. The main blog post says (and I quote) Still there remains the key question: is the proof correct? In one sense the present paper almost surely has mistakes—not just from the above objections but what one could expect of any first-draft in a breakthrough situation. The real questions are, is the proof strategy correct, and are the perceived gaps fixable? edit: the commenter Charanjit Jutla seems to know his stuff but I still maintain that an offhand comment does not warrant the definitive titling of your submission.
  - kvs 16y ago
    Do a quick search on the blogs and the names of people posting comments on it. They are authoritative sources, just because it is on a blog (run by a well known complexity theorist) doesn't mean it's less important. I am quite surprised to see so many comments from these guys and such a discussion happen in public.
    - studer 16y ago
      They don't necessarily agree with each other, though, so I'm not so sure how "authoritative" individual blog comments are (see e.g. Bradfield's followup to Jutla -- "And I don’t understand your comment about it not being known whether mu-calculus has a hierarchy of expressibility in alternation. It’s 15 years since I (and independently Lenzi) proved that it did!")

akshayubhat 16y ago

The mention of the paper has been removed from the authors homepage.

learner4life 16y ago

It is a bit sad though for the author. The author never intended the paper to be public. Now he joins the infamous list of people who published to prove P!=NP or otherwise.

zokier 16y ago
Well, to be fair, he didn't actually publish it. Especially not in the conventional meaning of scientific publishing.
- nsoonhui 16y ago
  Not sure if he wanted to he could get past the conventional meaning of peer review.
eegilbert 16y ago
Agreed. I would be pissed at whoever publicized a draft I had sent in a private email.
tomjen3 16y ago
It is sad for the author, but not because he will join that list - he is not. He is going to join the much less famous list of people who attempted to prove a very difficult problem, did so in a professional way, and while they ultimately failed they did advance science. And whomever leaked that is going to end up on the shitlist of an entire community of researchers.
joe_the_user 16y ago
If someone seriously wants to only share their P!=NP proof privately, they need to put "not for wide circulation" as a watermark on every page. But who know what the authors thinking was? Perhaps he hoped they'd share the paper only if they were sure it was right, perhaps he expected they wouldn't share it at all. Perhaps he expected they'd share it and he was already convinced the paper was correct. Perhaps he didn't care to what people outside the field thought...
- 16y ago

ewjordan 16y ago

Until a major chorus of experts chimes in with "Yup, this is curtains for this approach", I think it would be wise not to take too seriously any blog comments based on quick reactions to the paper. ...just as it would be unwise to take the paper itself too seriously until a chorus of experts tells us that it's looking pretty good.

noodle 16y ago
indeed. there are probably not many people on HN or people who are going to post comments on blogs that are qualified to actually weigh in on this type of thing.
deleted 16y ago
[deleted]
akshayubhat 16y ago
There are several indicators, the author of the comment seems to be a researcher at an IBM R&D center. Also the original author removed the paper from him web page. Thus which indicates that he is probably backing out on his claim.
- hubb 16y ago
  removing the paper doesn't necessarily mean that at all, he probably just wants finish editing it and getting peer feedback before he releases it officially
  - studer 16y ago
    Or maybe HP legal told him he couldn't use their web server to host unpublished material...
    - barkingcat 16y ago
      It would be extremely unwise of HP to shut him down - regardless of whether his proof works out in the end, this is a significant piece of work contributed for the further understanding of hard math problems - which is what HP ideally wants to represent. To say no to endeavours like this would be to say that they have no soul and no will for the enhancement of human knowledge.

tierack 16y ago

Whatever comes of this paper specifically, it's been a very entertaining couple of days to watch this unfold.

maqr 16y ago
I've been watching it the whole time, and I still have absolutely no idea what's going on.
- dschobel 16y ago
  SCIENCE!!! </zed shaw>

palish 16y ago

Could some math expert (cperciva?) read the paper, read this blog post, and tell us the results?

cperciva 16y ago
I've skimmed the paper, but it's way over my head. It would take me years of study to understand everything in this paper. (I'm confident that I could do so if I wanted to -- but my expertise lies in entirely different directions.)
- palish 16y ago
  Wow. It's so strange to realize how incredibly massive the field of mathematics is. As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. (Edit: of course, now I regret writing this. What I meant was: I can read, understand, and re-implement 99% of software engineering algorithms / architectures.) But to know that it would take someone as insanely experienced as cpervica years of study to understand that proof... Wow.
  - pmjordan 16y ago
    As a software developer, there isn't a single programming concept / architecture / algorithm / etc that I can't learn in less than a day. That's quite a bold claim.
    - palish 16y ago
      At this point, I have >10 years of programming experience. I've been programming for the majority of my childhood and the entirety of my adult life. I don't like to overestimate my own abilities, and I wish I could prove to you that my above claim is true. I simply have enough experience where I know for a fact that I can understand 99% of algorithms and architectures that were designed to solve a practical real-world problem. So you're right, "there isn't a single..." is probably pushing it. But I'd definitely stand by the fact that I can read, understand, and re-implement 99% of algorithms or architectures. My point is simply that the breadth of the field of software engineering apparently pales in comparison to that of mathematics. Or rather --- it's very strange to me that if you are an expert in a given branch of mathematics, then all of your lifetime of experiences cannot be applied to an entirely different branch. If I understand cperciva correctly, if you want to learn a particular specialized branch of mathematics, then you basically have to start from the ground-up (years). It would basically be equivalent to wiping your memory of all programming knowledge, then re-learning it all, in terms of effort. It's just strange / interesting that mathematics works that way.

gojomo 16y ago

P≠NPin' ain't easy.

kenjackson 16y ago
Anything goes when it comes to FOs, because ...
jberryman 16y ago
How long have you been waiting to write that?
kevinherron 16y ago
You seriously just made my day.
jasonwatkinspdx 16y ago
I normally don't vote up humor here because I like the snr, but this got me. Well played sir.
dunstad 16y ago
I'm afraid I've missed something here. Anyone care to provide an explanation?
- martincmartin 16y ago
  "Pimpin' ain't easy"
- deleted 16y ago
  [deleted]

troutwine 16y ago

Clearly I need to study more.

deleted 16y ago

[deleted]

jmatt 16y ago

All these academics that lay low then pop up with problems and call Deolalikar's contribution unfixable infuriate me. They bring out the worst in the same way that bad QA employees do. They create no wealth and add little value. They slow down and confuse the process. But in the end they are still necessary. There is something to be said about how one reports such problems. Most here know a great QA person that reports relevant problems in a intelligent manner and is there to help find solutions. Versus the QA person that just cranks out an endless stream of wonky insane problems. All make you look bad and all are difficult to reproduce, understand or address. It's my understanding that his approach is a radical and new way to attempt to solve the P!=NP problem. So it's no surprise that at first glance the vast majority of average math and computer scientists would think it was not a valid approach. And, again no surprise to me, that has ended up to be the case. I don't pretend to understand this flaw or Deolalikar's paper. But I do understand the type of person that posts comments like that... It looks like the math community has settle on a wiki to unofficially collect news and information on the paper: http://michaelnielsen.org/polymath1/index.php?title=Deolalikars_P!%3DNP_paper http://michaelnielsen.org/polymath1/index.php?title=Deolalik...

brent 16y ago
The claim is that the proof is unfixable. Proofs are either right or wrong. Good academics are supposed to checks proofs of their colleagues. There is no claim as to the merit of contributions made by Deolalikar. So, why exactly do these academics infuriate you?
- jmatt 16y ago
  So, why exactly do these academics infuriate you? I'm quite clear if you read more than one sentence. It's the way this guy responded to a comment of a blog about the paper. It just seems like a bad place to post a real unfixable flaw to the paper. Assuming the commenter is right (also possibly a bad assumption) why not put some effort into your response that will be read by every computer science and math person you'll ever work with in the future. For instance how does one respond, follow up, contact this guy? I have to go google him wtf. It's the equivalent to nitpicking. In the end someone else will have to pick up the pieces of what he said and analyze it and rewrite it and repost it. So to me he seems like the guy from QA that no one wants to work with - a bad team player.