Please create an account to participate in the Slashdot moderation system

 



Forgot your password?
typodupeerror
Math

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

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.
This discussion has been archived. No new comments can be posted.

Mathematicians Race To Debunk German Man Who Claimed To Solve The 'P Versus NP' Problem

Comments Filter:
  • by Anonymous Coward

    lol.

  • by Anonymous Coward

    P = NP iff P=0 or N=1

  • P != NP proof (Score:5, Informative)

    by bongey ( 974911 ) on Wednesday August 30, 2017 @03:06PM (#55112205)
    Paper is suggesting P!=NP .
  • Hmm this does not sound right, shuld the reaction not be: New thery, lut`s test it and see what the results are? when you set out to debunk something you are biased against it from the start. Or is this just a cas of the supmitter wanting tohave a slightly more confrontational title?
    • by bn-7bc ( 909819 )
      And of corse I forgot the other possibilitty, this German is obviosly wrong and evryone else is just rasing to brove it to shut him up and moving along. I am not qualified to even guess about it.
    • by Anonymous Coward

      Well, think about it ... this conjecture is literally decades old, possibly much older I can't remember off the top of my head.

      It has wide ranging implications if proven. Someone claims to have proven it. There's money on the line for proving it.

      The primary way to review this isn't to say "wow, that's awesome, it must be true" ... it's literally to attempt to invalidate the proof and say "yeah, but this is wrong right here and therefore everything after it is wrong".

      And claiming to be the one to have prov

    • by JohnFen ( 1641097 ) on Wednesday August 30, 2017 @03:29PM (#55112391)

      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.

    • by serviscope_minor ( 664417 ) on Wednesday August 30, 2017 @03:31PM (#55112415) Journal

      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.

      • No, it's maths, not science.

        That's irrelevant: we do exactly the same thing in science too. The only difference is that, in addition to looking for flaws in the logic, we can test a paper's assertions against data - either existing or new.

        • The only difference is that, in addition to looking for flaws in the logic, we can test a paper's assertions against data - either existing or new.

          You're basically saying the only difference is that they're completely different!

          • No it is the same with one additional constraint. Both maths and science papers have to be logically consistent but a science paper also has to agree with nature. If a paper is published claiming that a particular measurement will have a value X you can debunk it two ways. First you could find an error in the mathematical calculation of the value X and secondly, you could go and measure the value and find that it is not X. So it is just like maths with the additional constraint that the maths not only has t
        • The only difference is that, in addition to looking for flaws in the logic, we can test a paper's assertions against data - either existing or new.

          All the data suggests, very strongly, that P != NP. This is what the (known to be flawed; we've known for several days before Slashdot picked it up) paper claims. So the claim already matches the data.

          Given that the author is not a crank (most P?=NP papers are crankery), the only two possibilities are that the proof is valid or the proof has a flaw. The only way to tell is to look for flaws.

      • Or the proof itself is undecidable.
    • This is a mathematical proof not a scientific one. All you have to do find a flaw in the logic to disprove it.

    • by Anonymous Coward

      They used that terminology because Razborov (the author of the paper it's based on) has publicly stated that his method does not apply, so the proof is flawed.

      tl;dr: The proof has already been debunked.

    • I have a much easier proof that P != NP.

      If P was equal to NP then it would refer to its own proof as much as to anything else. In short, proving that P = NP would be just as easy as verifying that proof.

      Since proving that P = (or !=) NP is obviously hard, and since anyone working on the problem has been discredited inside a week, then that clearly shows that the proof is hard to calculate and easy to discredit. Ergo P != NP.

      I'll take that in cash please. Small bills.

      • Re: (Score:1, Informative)

        by Anonymous Coward

        While this argument seems to be partly in jest, Scott Aaronson even refers to it as reason #8 "The Self-Referential Argument" to believe P != NP.
        There is something weirdly fascinating about this kind of thinking.

        https://www.scottaaronson.com/blog/?p=122

    • There are a number of word-values here that are peculiar to mathematics, and probably giving the wrong opinion for a general audience. To many people, myself included, this reads a bit like the cold fusion debacle. But it isn't. With cold fusion there ought to be an experiment that others can repeat or not as the came may be, but many critical factors were omitted. With mathematics, the written analysis is everything.

      So, let's have a go at re-drafting the summary. Blum feels they have got somewhere with

  • by Anonymous Coward

    Andrew Wiles' first proof that solved Fermat's Last Theorem was initially flawed, but he was able to fix it within a year. I'm going to hold off judgement until 1) it's clear whether or not Blum's current proof is wrong, and 2) it whether or not it can be salvaged.

  • by MostAwesomeDude ( 980382 ) on Wednesday August 30, 2017 @03:17PM (#55112281) Homepage

    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.

    • by Myrdos ( 5031049 )

      Traveling Salesman instances can actually be solved in pretty good time due to a TSP-specific heuristic.

      Do you mean with branch and bound? Or is there something even faster?

      • by HuguesT ( 84078 )

        Basically B&B but with very good heuristics. We can solve TSP with 10^6 nodes without too much trouble.

    • by Megol ( 3135005 )

      One doesn't _solve_ things with heuristics so I don't know what you mean? One can get pretty good results for traveling salesman problems with good algorithms, approaching the optimal route - sure. But it isn't the same as solving the problem which would provide the optimal route every time. If one want the optimal route the problem is still hard.

    • by david_thornley ( 598059 ) on Wednesday August 30, 2017 @06:36PM (#55113401)

      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.

      • by gweihir ( 88907 )

        Chess is not finite. But since it is finite state, it must run into a state reached before eventually when playing it infinitely. Then you can sort-of say that the intermediary steps did not matter. However there is an infinite number of different chess games. All it takes for the proof is a state that you can go away from and go back to afterwards in two different ways. Then call one "0" and one "1" and encode all binary numbers in this. QED.

        • Re: (Score:3, Informative)

          by rgmoore ( 133276 )

          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 is also the 50 move rule, which puts a (very crude) upper bound on the length of any chess game at 49*15 = 735 moves.

      • by houghi ( 78078 )

        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

        To me that does not seem to be a special case. You take two things and think they are the same. One is shortest distance and one is shortest time.

        Anybody with a GPS will know that these are not the same. If A to B to C is 2 distance unit. It will be (assuming they are in a straight line) 4.
        If the time from A to B is 3 and from B to C is 3. and f

        • TSP is defined on an arbitrary graph, and we can fill in connection costs as we please.

          TSP is also defined as the lowest-cost way to visit each node once. It may be that A->C->B is less than A->B in the general case, but using that as a replacement means C cannot be used in any other order.

    • Re: (Score:3, Insightful)

      by gweihir ( 88907 )

      Indeed. And it may well turn out that if Blum did not solve it after all, his work provides a critical stepping stone or has other important uses (may take centuries though, Math is hard). This is mathematics at its best and practiced by some truly impressive minds.

    • Blum is a respected mathematician who has been working in this subfield for years, [...]

      That, by the way, is the only reason why this has made news this time around. Even though his purported proof was likely to be flawed, assuming that anyone in this generation is going to solve the problem, Blum is the sort of person who may be able to do it or, even if he can't, to make progress even with a flawed proof.

  • by Anonymous Coward

    Scott Aaronson dd not bet 200000 $ . He basically said he's tried of people asking about P != NP . He explains so much in the very blog linked from TFA:

    A final thing to talk about—yeah, we can’t avoid it—is Norbert Blum’s claimed proof of P != NP. I suppose I should be gratified that, after my last post, there were commenters who said, “OK, but enough about gender politics—what about P vs. NP?” Here’s what I wrote on Tuesday the 15th:

    To everyone who keeps asking me about the “new” P != NP proof: I’d again bet $200,000 that the paper won’t stand, except that the last time I tried that, it didn’t achieve its purpose, which was to get people to stop asking me about it. So: please stop asking, and if the thing hasn’t been refuted by the end of the week, you can come back and tell me I was a closed-minded fool.

    Many people misunderstood me to be saying that I’d again bet $200,000, even though the sentence said the exact opposite. Maybe I should’ve said: I’m searching in vain for the right way to teach the nerd world to get less excited about these claims, to have the same reaction that the experts do, which is ‘oh boy, not another one’—which doesn’t mean that you know the error, or even that there is an error, but just means that you know the history.

  • Solve is not a noun.
    • Solve is not a noun.

      <sarcasm effect="gagging">
      Don't you know? If you actually take into account parts of speech in your grammar, you are not cool and techy! I can receive an "invite" to a "consult", but if I fail to show up I can have another "go".

      Clearly your "know" is bad and your "learn" is insufficient. Next time, first find out more about "speak"!
      </sarcasm>

  • I guess he created meta N = NP problem.
  • P ~ NP

    and call it a day. Problem solved.

  • by UnixUnix ( 1149659 ) on Wednesday August 30, 2017 @04:27PM (#55112741) Homepage
    Blum's approach does not fall prey to the known barriers of relativization, natural proofs and algebrization, it's a serious and inspiring effort that unfortunately does have a flaw and it's unclear whether it can be fixed. The reason many in the field are skeptical is this: experience with long-term outstanding open problems indicates they need some major overall advance in Mathematics as they don't yield to clever twists of the currently known, e.g. Fermat's Last Theorem took hundreds of years and advances two orders of magnitude beyond what was known in Fermat's time before the (complicated) proof by Wiles. The P, NP, PSPACE matter shows our understanding of these fundamental complexity classes is still rather superficial. So we just post on /.
  • Whenever one of the remaining really large mathematical questions gets a credible attempt at solving it, this is the standard procedure. The author publishes, some reputable people in this area do a sniff-test and say "this deserves real consideration" and then it takes a while (pften years) to figure it out. I would also like to point out that we have seen credible but faulty proofs for big questions in the past that then later actually could be fixed or serve as basis for a real proof. Hence this is an im

  • It is good to have doubts, especially for such topics, like P vs. NP. However, doubts are not the equivalent to error. Therefore, we have to wait until mathematicians have come to a definitive answer.

  • This is effectively peer-reviewed science & mathematics doing its job.

    Academic publishes potential proof of extremely well-known and difficult problem in mathematics.

    Other academics examine proof to see if it contains errors (even though many would hope it doesn't and this famous problem can be solved).

    It looks like it does.

    Submitter goes away and tries to fix errors.

    Repeat until successful/dead (delete as applicable).

  • Yesterday he posted this comment to the Cornell page linked above: "The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage"

  • Blum has updated the comments for the proof on the official publication site [arxiv.org].

    Comments: The proof is wrong. I shall elaborate precisely what the mistake is. For doing this, I need some time. I shall put the explanation on my homepage

Lo! Men have become the tool of their tools. -- Henry David Thoreau

Working...