Slashdot Mirror

← Back to Stories (view on slashdot.org)

Mathematicians Race To Debunk German Man Who Claimed To Solve The 'P Versus NP' Problem (vice.com)

Posted by msmash on from the let-the-debate-begin dept.

A German man -- Norbert Blum -- who claimed that P is not equal to NP is seeing several challenges to his solution. From a report: Numerous mathematicians have begun to raise questions about whether the German mathematician solved it at all. Since Blum's paper was published, mathematicians and computer scientists worldwide have been racking their brains as to whether the Bonn-based researcher has, in fact, solved this Millennium Prize Problem. After an initially positive reaction, such as the one from Stanford mathematician Reza Zadeh, doubts are beginning to arise about whether Blum's reasoning is correct. In a forum for theoretical mathematics, a user named Mikhail reached out to Alexander Razborov -- the author of the paper on which Blum's proof is based -- to ask him about Blum's paper. Razborov purports to have discovered an error in Blum's paper: Blum's main argument contradicts one of Razborov's key assumptions. And mathematician Scott Aaronson, who is something of an authority in the math community when it comes to P vs. NP, said he would be willing to bet $200,000 that Blum's mathematical proof won't endure. "Please stop asking," Aaronson writes. If the proof hasn't been refuted, "you can come back and tell me I was a closed-minded fool." In the week since Aaronson's initial blog post, other mathematicians have begun trying to poke holes in Blum's proof. Dick Lipton, a computer science professor at Georgia Tech, wrote in a blog post that Blum's proof "passes many filters of seriousness," but suggested there may be some problems with it. A commenter on that blog post, known only as "vloodin," noted that there was a "single error on a subtle point" in the proof; other mathematicians have since chimed in and confirmed vloodin's initial analysis, and so the emerging consensus among many mathematicians is that a solve for P vs. NP remains elusive.

12 of 156 comments (clear)

  1. Re:Summary doesn't give the answer by vux984 · · Score: 3, Informative

    He might have proved that P != NP.

    And this is the result we expect. So proving it would confirm most suspicions, but it should go without saying that searching for flaws in this proof is good mathematics, and exactly what everyone should be doing.

  2. Re:P not equal NP [Re:Summary doesn't give the an. by XXongo · · Score: 5, Funny

    Oh, so it's implied but not proven. Gotcha.

    Mathematicians may read different things from the word "imply" than you do.

  3. P != NP proof by bongey · · Score: 4, Informative

    Paper is suggesting P!=NP .

  4. As usual, journalists don't grok mathematicians by MostAwesomeDude · · Score: 4, Informative

    Nobody is racing, Scott Aaronson did not make a monetary wager this time around (and was also rudely misquoted), Blum is a respected mathematician who has been working in this subfield for years, most mathematicians expect that P != NP and also that the proof will be very difficult and not found by accidental observation like in Blum's paper, chess is within EXPTIME and not "out of the realm of possibility", and Traveling Salesman instances can actually be solved in pretty good time due to a TSP-specific heuristic.

    --
    ~ C.
    1. Re:As usual, journalists don't grok mathematicians by swillden · · Score: 5, Informative

      He was talking about P!=NP. Almost no mathematician believes that P=NP. Notable exception: Donald Knuth once expressed your point of view.

      As I recall, what Knuth said was that the worst possible solution of the P/NP question would be a non-constructive proof that P=NP. That would tell us that all problems are "easy", but not tell us anything about how to solve them efficiently. It would mean that we could never rely on problems to be hard where we want them to (e.g. cryptography), but wouldn't necessarily give us any insight about how to make them easy.

      I don't think he ever expressed the opinion that he thought it likely that P=NP.

      --
      Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
    2. Re:As usual, journalists don't grok mathematicians by david_thornley · · Score: 4, Insightful

      Technically, chess can be completely analyzed in O(1), since it's a finite problem.

      You can't solve general Traveling Salesman problems in polynomial time. It may be possible to do special cases*, and it is possible to come up with heuristics that will give you a good solution but not necessarily the optimal one.

      In general, if you prove that a problem is NP-complete or NP-hard, you give up on finding an efficient exact solution and start looking for special cases and good heuristics.

      *One special case is where the shortest distance from A to B is the direct line from A to B; that is, you can't go from A to C to B faster than you can go from A to B. This is what you'd normally expect, but it doesn't always hold. If A and B are in unfriendly countries, and C is in a neutral country, it may indeed be faster to go A->C->B than A->B directly.

      --
      "When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
    3. Re:As usual, journalists don't grok mathematicians by rgmoore · · Score: 3, Informative

      This is incorrect. There's a rule in chess that the game is a draw if the same position is reached three times. Since there are a finite number of possible positions and a you're only allowed to visit each of those positions a finite number of times in a game, there must also be a finite number of games.

      --

      There's no point in questioning authority if you aren't going to listen to the answers.

  5. Re:Mathematicians Race To Debunk by JohnFen · · Score: 4, Insightful

    when you set out to debunk something you are biased against it from the start.

    Yes, which in this sort of thing is exactly the right stance to take. you want to intentionally look for ways that the theory is incorrect because, if the theory is correct, it doesn't matter how biased you are. The theory will survive.

    However if you don't start off with the intention of disproving it, then you might miss the critical bit that show the theory to be wrong.

  6. Re:Mathematicians Race To Debunk by serviscope_minor · · Score: 5, Insightful

    Hmm this does not sound right,

    It is.

    shuld the reaction not be: New thery, lut`s test it and see what the results are?

    No, it's maths, not science. There is an absolute truth here. Either the proof is correct or it is not. The best way of figuring out if it's correct is to look for flaws.

    --
    SJW n. One who posts facts.
  7. Re:Summary doesn't give the answer by vux984 · · Score: 4, Interesting

    Proving that P!=NP only requires proof of one polynomial problem not being deterministic, it doesn't matter what it is, and it's proven.
    Proving that P=NP, on the other hand, might be impossible without a new definition of polynomial.

    I believe you are mistaken.

    Finding one example of P = NP proves the classes are equal, because NP-complete problems can all be transformed to other NP problems in polynomial time.

    So if you solve ANY NP-complete problem in polynomial time, you have a solution to ALL of them. If you solve 3-SAT in polynomial time you've solved TSP (travelling salesman) in polynomial time too, because TSP can be "mapped" to 3-SAT in polynomial time.

    So basically, if you can prove OR disprove any NP-complete problem can be solved in polynomial time then you prove P=NP or P!=NP.

  8. Re:Summary doesn't give the answer by vux984 · · Score: 3, Interesting

    https://en.wikipedia.org/wiki/...

    If he finds a solution in polynomial time of ANY NP-complete problem he proves P=NP.

    By the definition of NP-complete:

    "A problem p in NP is NP-complete if every other problem in NP can be transformed (or reduced) into p in polynomial time." (This makes sense, because if you can got from A to B in polytime, and A to C in polytime then you can go from A to C in polytime too, trviially by going from A to B and then B to C. (because polytime x polytime = polytime)

    A P=NP proof would consist of finding a polynomial solution to *any* NP-complete problem (and therefore ALL NP-complete problems.)

    There are a handful of problems in NP that are not known to be in P and not known to be NP-complete; but if P=NP they would also have polynomial time solutions.

    NP-hard problems are NOT in NP. (e.g the halting problem) so they aren't at issue.

    A P != NP proof is the harder proof since you can't use proof by example -- you have to formally prove that a polynomial solution does not exist for an NP-complete problem. (and therefore does not exist for all of them)

  9. Re:Early Confirmation Bias by Zalbik · · Score: 3, Funny

    You don't "test" math proofs. They are either true, or they are not. If they have errors, then you got good ol' TPATWTCIF.

    Wait, are you saying the P vs NP proof is not verifiable in polynomial time? :-)