back to article P≠NP proof fails, Bonn boffin admits

Computer science boffin Norbert Blum has acknowledged that his P≠NP proof is incorrect, as a number of experts anticipated. In a post published Wednesday to the arXiv.org page where his paper used to be, Blum, a computer science professor at the University of Bonn, said: "The proof is wrong. I shall elaborate precisely what …

  1. Anonymous Coward
    Anonymous Coward

    For one moment I read it as the Claymation institute.

    Yes, I am sad.

    1. Dz

      Re: For one moment I read it as the Claymation institute.

      Haha, that's exactly what happened to me too.

  2. ThaumaTechnician

    I slogged through that paper - for nothing?!!

    /didn't really.

  3. Joe Werner Silver badge

    That's why I usually bet against these things

    Not this time, though.

    My thinking is that it's unlikely to be true, and if it's true I'll be so amazed and happy that I don't mind losing the money.

    But I like the Bayesian look at this. The prior is really quite informative in his algorithm ;)

  4. Anonymous Coward
    Anonymous Coward

    Of course P≠NP....

    There's an extra N in front. Duh!

    1. Adam 1

      Re: Of course P≠NP....

      The proof was much closer than it sounds though. It held for all values of N except N==1.

      B+ Good effort

      1. ArrZarr Silver badge

        Re: Of course P≠NP....

        so does that mean all we need now is a proof for N==1 and combine the two, potentially?

      2. DJ Smiley

        Re: Of course P≠NP....

        .... did he forget to test for 0, 1 and other obvious examples then? :/

        1. Rich 11

          Re: Of course P≠NP....

          That would have taken too long.

  5. John Smith 19 Gold badge
    Unhappy

    Oh well, Every failure is a dress rehersal for success. *

    Thing is it seems that attempts to prove and disprove the conjecture have failed.

    So the fails are not biasing the result, Bayesian style, toward a particular direction.

    Although strictly speaking even failures are fine, if they teach you something more about the solution space, IE where a solution (if it exists at all) must be found.

    1. Destroy All Monsters Silver badge

      Re: Oh well, Every failure is a dress rehersal for success. *

      As said previously, it probably is not a mathematical problem at all, so there may well not BE a solution space.

      "Prove that c = 1".

      Well, duh!

      1. Anonymous Coward Silver badge
        Boffin

        Re: Oh well, Every failure is a dress rehersal for success. *

        As part of my A-level advanced mathematics, I had to prove that 1≠2

        By the way, c=299792458m/s. If you want to specify that c=1, you need to add the units VP (Planck velocity)

        1. Anonymous Coward
          Anonymous Coward

          Re: Oh well, Every failure is a dress rehersal for success. *

          Could it be that P≠NP is unprovable; and if so, could someone prove this to be the case?

          1. Wandering Reader

            Re: Oh well, Every failure is a dress rehersal for success. *

            "Could it be that P≠NP is unprovable; and if so, could someone prove this to be the case?"

            I can't prove it, but if someone could find a proof, it can be checked.

          2. stephanh

            Re: Oh well, Every failure is a dress rehersal for success. *

            "Could it be that P≠NP is unprovable."

            That would be possible. From a practical point of view, the consequences would be not so different from a proof that P≠NP. It would still mean that you cannot have an actual polynomial-time algorithm to solve, say, the traveling salesman problem (because any such algorithm would immediately be a proof that P=NP).

            However, it would mean that *assuming* that such an algorithm exists (even though you don't know it) cannot lead you to a logical contradiction.

            "and if so, could someone prove this to be the case?"

            I take this as a question if proving this would be possible, and not as a request to provide the proof. If so, then yes, provided it is actually true ;-)

            By the way, it would be really tantalizing if somebody would prove P=NP but in a non-constructive way, i.e. proving that all NP problems can be solved in polynomial time but providing absolutely no clue about *how* to achieve this...

            1. Claptrap314 Silver badge

              Re: Oh well, Every failure is a dress rehersal for success. *

              I've not gone anywhere near the problem myself, but intuitively, the proof almost has to be nonconstructive. A constructive proof would mean that given any validation algorithm, you construct an algorithm of proof with the same (or better) O(n) characteristic.

              This feels---preposterous.

        2. Paul Kinsler

          Re: c=299792458m/s. If you want to specify that c=1, you ...

          ... are probably just a theoretical physicist, where setting c=1 is entirely legitimate and frequently the most convenient thing to do.

          This is distinct from various preliminary "back of the envelope" scrawlings where you might also have 1=c=hbar=pi=e=2=-1 :-)

        3. DropBear

          Re: Oh well, Every failure is a dress rehersal for success. *

          "I had to prove that 1≠2"

          While this is understandably startling for the layman, a mathematician would just immediately propose the opposite assumption ("1=2") and drive it straight into the nearest impossibility using only rigorous logic on the way. Done. Not that I have any idea what that might be, mind, but hey I'm not a mathematician...

          1. PlinkerTind

            Re: Oh well, Every failure is a dress rehersal for success. *

            "...While this is understandably startling for the layman, a mathematician would just immediately propose the opposite assumption ("1=2") and drive it straight into the nearest impossibility using only rigorous logic on the way...."

            Bertrand Russell held a lecture once, where he said:

            -If you assume one single errornous piece as a fact, then you can prove anything!

            -I dont belive you. If you assume that 1=2, can you prove that... you are the pope??

            -The proof is trivial. I and the pope are 2 different persons, which means we are 1 person by (the faulty) assumption. Hence, I am the pope.

  6. Destroy All Monsters Silver badge

    Let them eat Clay!

    The Clay Mathematics Institute is offering $1m in prize money for solutions to these problems.

    The Clay Mathematics Institute is silly because if some has the solution (as long as it is constructive) he would be RAKING it in and probably take over the very living brains of the Clay Institute Members by midnight.

    Say Brain, what do you want to do tonight?

    The same we do every day Pinky: Try to prove P=NP!

    ARF!

    1. veti Silver badge

      Re: Let them eat Clay!

      I don't think "proving that P != NP" would let anyone "rake it in". Everyone already assumes that's the case, so proving it is just a formality - a big intellectual challenge, but in practical terms it would make sod all difference to anything.

      Now, if you could prove the opposite, that would be something else entirely.

      1. Dave 126 Silver badge

        Re: Let them eat Clay!

        > Now, if you could prove the opposite, that would be something else entirely.

        Yep, that would be the premise of the film Sneakers, starring Robert Redford as a pen tester, and James Earl Jones as head of a three-letter agency. Supporting cast includes Ben Kingsley, River Pheonix, Mary McDonnell, Dan Akroyd and Sidney Poitier.

  7. maccy
    Happy

    Respect to Prof Blum ...

    ... for having a homepage that doesn't look like it has changed much since Netscape was the browser of choice.

    Probably has more important things to do.

    1. find users who cut cat tail

      Re: Respect to Prof Blum ...

      I may look so, but without JS it is just an blank page. So it's still one of those modern ‘we absolutely cannot make a text entry and a button without JS’ sites...

  8. streaky

    Number of people shocked/surprised:

    0

    Yeah exactly.

  9. Karlis 1
    Pint

    Bayesian? What is this, 2002?

    Surely they meant to say "Analysing via means of real-time driven big-data machine learning utilising state of the art infrastructure of our sponsors at Azure - providers of the most stable and scalable cloud computing infrastructure for unprecedented super-computing tasks for tomorrows demanding research effort..."

    (of fuck it, I'm only on my second coffee and couldn't continue in fears of throwing up. I'm so sorry mum. I couldn't help. It's the commies fault!)

    Where is that bottle of scotch?

    1. John Brown (no body) Silver badge
      Thumb Up

      Re: Bayesian? What is this, 2002?

      You forgot to work in "leading edge A.I."

      PS, pour me one while you're there.

  10. John Smith 19 Gold badge
    Unhappy

    Odds on bet was it was always going to fail. But...

    a proof, one way or the other, should be possible.

    IOW the question should be "decidable"

    Didn't say what it was.

    Didn't say how to get it.

    Say that a proof (one way or the other) should be possible.

    But do logicians even know this?

    1. John Smith 19 Gold badge
      Unhappy

      "But do logicians even know this?"

      As in is the question is N<> NP decidable?

      I've been presuming that it has been proven that an answer is possible, even if we don't know what it is.

      But what if it isn't?

      I know this sounds like one of those "how many angels can dance on the head of a pin" questions but if it really is undecidable (as the halting problem is) then we seem kind of f**ked.

      And I'm not enough of a logician to know if it is.

      1. Claptrap314 Silver badge

        Re: "But do logicians even know this?"

        We know that there are true statements that cannot be proven. IMHO, this is in the class of problems which might, just might, actually be unprovable. So yes, either P == NP, or P != NP, but we might also get a proof that we cannot prove P == NP (or not) with standard set theory. Oddly enough, the latter might be provable with standard set theory....

  11. teknopaul

    sha256 hash

    a class of problems where it's easy to check the solution, but it's difficult to come up with a solution.

    no? do I win the prize?

    1. Dave 126 Silver badge

      Re: sha256 hash

      No, because to win the prize you can't merely demonstrate that you can't do it; you must prove that nobody can do it ever.

    2. Tom Melly

      Re: sha256 hash

      The point, afaik, is that we can't be sure that it's difficult to come up with a solution.

    3. DropBear

      Re: sha256 hash

      Easy to misunderstand issue, because _on face value_ the way it's stated in the article is flat out ridiculous (_of course_ there are problems that are hard to solve but easy to check, we have a list of examples, with factoring to primes right on the top); that said, even in that form, the question is actually perfectly valid, asking whether there really is no easy way to solve such problems, ever, or whether it's only hard because we have no idea how to do it easily, yet.

  12. DontFeedTheTrolls
    Coat

    Next he's going to prove black is white and will probably be killed on a Zebra crossing

  13. Anonymous Coward
    Boffin

    What's the MSFT angle?

    Configuring Office 365 securely is certainly an NP-hard problem!

  14. JacobZ
    Trollface

    I have a remarkable proof...

    ...that P!=NP is formally undecidable within axiomatic arithmetic. Unfortunately, the proof is too long to fit in this margin.

    1. You aint sin me, roit

      Re: I have a remarkable proof...

      If it weren't for the smallness of Mr Fermat's margins we wouldn't have a whole bunch of number theory, not least Galois Theory - even though those discoveries were obtained while failing to prove the theorem.

      I wonder what advances have come from all the failed attempts to prove P=NP, or otherwise.

  15. Forget It
    Joke

    P = Pudding

    NP = No Pudding

    The proof is in the Pudding.

    QED

  16. stephanh

    I don't agree with the jadedness

    There are of course tons of crackpots who come up with their "proofs" that P is or is not NP, but this was a real Comp.Sci. professor from a respectable university. Obviously the odds where still that there was a mistake, but I think it was justified to take notice this time.

  17. jhonhardw

    P = NP

    Great News.

    Andri Lopez presents the algoritm to factor all odd numbers.

    Affirming that: IF, P = NP.

    Published in:

    http://www.ceser.in/ceserp/index.php/IJEFT/article/view5560/0

  18. This post has been deleted by its author

  19. Anonymous Coward
    Anonymous Coward

    Believing too much might have hindered the development of science.

    For the P vs. NP problem, almost all researchers believe P = NP. And this problem is still unsolved. If P = NP, this bias would be a significant loss. I submitted a paper claiming P = NP to STOC 2020 and was rejected with an only comment of “doubtful.” I rewrote it and opened it on a site, it achieved over 2500 accesses in only two days. It could exceed 100 accesses per hour. This access speed is a bit unusual, says a researcher in other fields. If you glance at my paper, you will see that I am seriously researching.

    https://www.researchgate.net/publication/339627657_Extract_maximum_independent_set_using_eigenvalue_relation?channel=doi&linkId=5e5d20efa6fdccbeba12d7c6&showFulltext=true

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon