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.
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."
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.
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 .
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.
Well, no, I know a few people who should not be doing this.
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.
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.
The article doesn't give the answer because, right now, nobody knows. People are working on determining if his proof is correct or not. That's pretty much all the article is saying.
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.
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.
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.
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.
The way I understand it, NP problems can all be transformed to other NP problems in polynomial time, but cannot be transformed to all other NP problems in polynomial time. So you would at most move a class of problems from NP to P.
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 /.
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)
Scroll down to consequences:
https://en.m.wikipedia.org/wik...
"So long and thanks for all the fish."
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.
Wait, are you saying the P vs NP proof is not verifiable in polynomial time? :-)
My understanding is that NP-hard are problems that are in the same class as NP-complete problems. Since any NP problem can be solved in exponential time, problems that are not solvable in exponential time (or at all) aren't NP-hard.
One example of an NP-hard program is the Traveling Salesman problem, which is to find an optimal route through a graph. If a problem is in NP, then you can efficiently verify a proposed solution, but (unless P=NP) you can't efficiently verify that a route is optimal. Now, take that graph and see if you can find a route with a cost less than some given value. This is in NP, since you can verify a proposed solution efficiently, and the Salesman problem can be solved in polynomial time if the modified problem can be. Obviously, the modified problem can be solved in polynomial time if the Salesman problem can be. We've determined that the modified problem is NP-complete, so we'd consider the Salesman problem as NP-hard.
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
You can test mathematical theorems, usually, by looking for counterexamples. If you find one, the proof is invalid. If you don't, that doesn't tell you anything about the validity.
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
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
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.
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.
sub f{($f)=@_;print"$f(q{$f});";}f(q{sub f{($f)=@_;print"$f(q{$f});";}f});
Actually, in math I think a closed mind is often more helpful than an open mind. That way you don't give up so easily. It's not as if math proofs aren't generally reasonably easy to validate...I believe it can even be done mechanically. Constructing the proof is a lot more difficult.
The only difficulty with this is when new approaches are used. In that case it can (and has in the recent past) require years of effort to translate the new approach into the older methods. And, of course, the proof checkers need to be able to validate the theorems and corollaries referenced. I believe this was a problem in the case I'm referring to because the references were all in Japanese math journals, and the proof engines weren't familiar with them. I should remember the guy's name, but I'm monolingual English and Japanese names just don't stick easily. And when it comes to math, I'm a programmer. I haven't even remembered enough details to google it. (And I am talking about using the Google search engine, it's not a generic reference.)
I think we've pushed this "anyone can grow up to be president" thing too far.
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 P != NP. He is unlikely to just trust his own intuition, so the work has probably had several reviewers by the time he feels confident enough to go public. At which point he probably still feels there may be errors that more eyes will spot, but right or wrong, this is something that people should be looking at.
And look they do. If he has really slain this monster, it will probably take a year or so of hard looking before most mathematicians will provisionally accept it. And even then they will keep poking.
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"