Slashdot Mirror
Mathematicians Race To Debunk German Man Who Claimed To Solve The 'P Versus NP' Problem (vice.com)
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.
So did he prove P = NP or P != NP?
Either way, it apparently is close enough so let's please move on.
lol.
P = NP iff P=0 or N=1
The previous /. post gave a link to the abstract, which is only three sentences long, here: https://arxiv.org/abs/1708.034.... The third sentence is "This implies P not equal NP."
The state of modern, Western political discourse makes me drink heavily.
After he's done cleaning the closet, troubleshooting the keyboard, shitposting Amazon affiliate links, he'll quickly glance over this proof and find all the mistakes lesser minds have made.
Behold the superior intellect of a IT miracle worker.
Oh, so it's implied but not proven. Gotcha.
Mathematicians may read different things from the word "imply" than you do.
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?
I was reading a book last month which inspired the proof. I noted the proof in the margin of the book but there wasn't enough room to write the proof in full.
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.
The state of modern, Western political discourse makes me drink heavily.
Me too. In fairness though, I was doing it anyway. Now I have an excuse.
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.
You sound preoccupied.
"Old man yells at systemd"
The state of modern, Western political discourse makes me drink heavily.
Don't be like that - I'm sure it has its bad points too.
I'm a minority race. Save your vitriol for white people.
We need a new elegantly caustic mod category just to be fair with your comment. LOL.
Custom Solvers 2.0 = Alvaro Carballo Garcia = varocarbas.
fuck off back to breitbart you stupid little dipshit
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.
+1 insightful
Solve is not a noun.
http://haspvsnpbeensolved.com
Razborov purports to have discovered an error in Blum's paper
Are you implying Razborov's claim is likely false?
I guess he created meta N = NP problem.
I mean, what is the significance of this proof to the world? Will it lead to some scientific or technological breakthrough?
If it's Lennart Poeterring we should just take hi's word for it. No cheese for the luddite's!
--
thegarbzage
This article smacks of early confirmation bias. It seems like the "peers," instead of testing the new theoretical proof, are instead simply looking for errors in it
...which is exactly how you test a mathematical proof.
It seems like the "peers," instead of testing the new theoretical proof, are instead simply looking for errors in it because they refuse to believe that someone has solved it when they could not.
You don't "test" math proofs. They are either true, or they are not. If they have errors, then you got good ol' TPATWTCIF.
P ~ NP
and call it a day. Problem solved.
It must have been something you assimilated. . . .
The previous /. post gave a link to the abstract, which is only three sentences long, here: https://arxiv.org/abs/1708.034.... The third sentence is "This implies P not equal NP."
Points for style, gotta give him that much. "Other guys demonstrated abstruse technical thing. We demonstrate another variant of abstruse technical thing. This implies P not equal NP."
Of course, he probably could have been even more restrained. I imagine that to people in the field the fact that the monotone and non-monotone network complexities of the clique function having the same bounds obviously implied P != NP, so he could have left the sentence out entirely, which would have been even cooler.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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 /.
Debunk or der Bunker?
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
I had a Real Analysis professor who told the Story of why there is no Nobel Prize in Mathematics.
Nobel's wife had an affair with A Mathematics Professor...
is this more or less juicy than your theory?
Wait, are you saying the P vs NP proof is not verifiable in polynomial time? :-)
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 important step either way and even if it requires a few years to fix, there may be a shared Field-Medal or similar in it for Blum and the answer to the P/NP question for everybody else.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
On the frightening premise that you may be serious:
Of COURSE they're looking for errors. That's what mathematicians do. If they see a complicated proof, they look for possible errors, because otherwise it's easy to miss them. It has nothing to do with refusing to believe.
If you can dig up a copy of Euclid, look at the very first proof, Proposition 1 of Book 1. If you just look at it, it looks convincing. If you are looking for errors, you are likely to find the error. If you just accept the proof as valid because it looks valid, you're wrong. Look for weak spots. Try counterexamples.
Errors aren't necessarily fatal to the overall idea of a proof. If one derivation or assumption in a proof is invalid, it might well be possible to find an alternative to the erroneous part. This happens, and when the errors have been fixed (if fixable) the proof is valid.
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
Actually, testing them (looking for a counterexample) is a quite standard technique when trying to evaluate the validity of a mathematical proof. This also one of the techniques used to understand it, and for stuff this advanced it can take months or years to get the gist.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
<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>
404555974007725459910684486621289147856453481154 in hex is "You sank my Battleship?"
[GPG key in journal]
The rule says that either player may claim a draw; it's not automatic.
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.
Smash the Fash! Free nose-jobs for Nazis!
And it's only a theory.
Same thing in maths.
"P implies Q"
means "if P is true then Q is true".
All I want is a secure system where it's easy to do anything I want. Is that too much to ask ~~ Randall Munroe
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).
It's not you: I'm just this horrifically socially awkward with everybody.
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"
Nah, that's just playing with semantics. It's also not a productive approach here - after 60 years of searching nobody has managed to find a single counterexample to P!=NP.
Blum has updated the comments for the proof on the official publication site.
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
Let German Man bunk! German Man need sleep after complicated proof!
Norbert Blüm claimed 30 years ago that "pensions are safe". And now he claims that P=NP. I'm not surprised.
Its not quite the same.. in math, "implies" is a strict "if P is true then Q is true" phrase as you wrote, while in English it tends to be read more along the lines of "P suggests Q," with a silent "but doesn't prove it" clause.
Its kind along the lines of how in English, "or" almost always means "exclusive or" while in math it definitely does not -- the concepts are related to be sure, but not exactly the same and mathematicians can't work with those inexacts so they use words in a much stricter sense (at least when being formal) than your average English speaker/writer ever would.