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.
"theoretical mathematics" (Score:1)
lol.
Re: (Score:2)
I handed a homework paper to my teacher and told him my score should be a theoretical 93%.
Obligatory (Score:1)
P = NP iff P=0 or N=1
Re: (Score:2)
Syntax error on line 1.
Re: (Score:2)
iff=If and only if.
Re: (Score:2)
Syntax error on line 1.
Re: (Score:1)
P != NP proof (Score:5, Informative)
Mathematicians Race To Debunk (Score:1)
Re: (Score:1)
Re: (Score:1)
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
Re:Mathematicians Race To Debunk (Score:5, 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.
Re:Mathematicians Race To Debunk (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.
Re: (Score:3)
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.
Re: (Score:2)
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!
Re: (Score:2)
Re: (Score:3)
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.
Re: (Score:2)
Re: (Score:2)
Ha! Very good :)
Though if it is undecidable then the proof that P!=NP must surely contain an error.
Re: (Score:2)
Then its not a proof.
Re: (Score:2)
That's not what the incompleteness theorem says. It says:
Any sufficiently complex system has true statements that cannot be proven true within the system.
This is not the same as statements which are both true and false. If there are statements which are both true and false then the system is not necessarily incomplete, but merely inconsistent. (It may also be incomplete.)
Re: (Score:2)
An important corollary: those true statements that aren't provable within their own system could still be provable within a larger system. For a really simple example, "1+1=2" is not provable within a system that consists entirely of real numbers and the "basic" high school level operators (such as addition) -- all you can do is define addition such that the statement is true and treat it essentially as an axiom from that point on. But it is provable within ZFC if you define your sets and operations corr
Re: (Score:2)
This is a mathematical proof not a scientific one. All you have to do find a flaw in the logic to disprove it.
Re: (Score:1)
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, much easier proof that P != NP (Score:2, Informative)
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)
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
Re: (Score:3)
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
Re: (Score:2)
Re: (Score:2)
Probably more than zero.
Ask ISIS, they'd know.
Re: (Score:2)
I'd assume all of them. It's hard to fly with only a left wing.
Re: (Score:3)
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.
Re: (Score:1)
Re: (Score:3)
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 checker
Re: (Score:1)
maybe (Score:1)
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.
As usual, journalists don't grok mathematicians (Score:5, 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.
Re: (Score:1)
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?
Re: (Score:2)
Basically B&B but with very good heuristics. We can solve TSP with 10^6 nodes without too much trouble.
Re: (Score:3)
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.
Re:As usual, journalists don't grok mathematicians (Score:5, 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.
Re: (Score:2)
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)
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.
Re: (Score:2)
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.
Re: (Score:2)
Ah, yes. I did think about the multiplication by two, but then thought that it was due to a "move" being both players' turns.
Just for comparison, the best known lower bound on the longest chess game is 545 moves. Either way, the point is that there are a finite number of chess games.
Re: (Score:2)
Either way, the point is that there are a finite number of chess games.
You are right but for the wrong reason: as both the draw by repetition and 50-move rule are only draws if claimed as such they don't actually place an upper limit on the game.
However, I learnt something new today: the 75 move rule and 5 times repetition rule automatically end the game in a draw. So, it's true there a a finite number of chess games but only since 2014 when the laws were amended.
Re: (Score:2)
Re: (Score:2)
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:2)
Interesting. However, unlike Go or checkers, chess doesn't scale up per se. There have been chess variants that used bigger boards, but they had new pieces.
Given a rule for scaling up chess, apparently (according to the stack exchange question you cited), it's PSPACE-hard, which isn't quite the same as EXPTIME-hard (I'm not offhand very familiar with the complexity hierarchy above NP, but you should be able to use exponential rather than polynomial space given exponential time.)
Re: (Score:3, Insightful)
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.
Re: (Score:2)
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.
Re:As usual, journalists don't grok mathematicians (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.
Re: (Score:2)
Scott Aaronson did not bet anything (Score:1)
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.
A solve... remains elusive. (Score:2)
who cares about parts of speech? (Score:2)
<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>
Re: (Score:2)
did he loop mathematicians? (Score:2)
Maybe we should just settle on ... (Score:2)
P ~ NP
and call it a day. Problem solved.
Elusive indeed (Score:3)
This is perfectly normal (Score:2)
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
Doubts? (Score:2)
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.
There's no story here, really (Score:2)
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).
Blum: "The proof is wrong." (Score:2)
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"
UPDATE: Blum now claims his proof was wrong (Score:1)
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
P not equal NP [Re:Summary doesn't give the an...] (Score:3)
Re: (Score:2)
The previous /. post gave a link to the abstract, which is only three sentences long, here: https://arxiv.org/abs/1708.034... [arxiv.org]. 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.
Re:P not equal NP [Re:Summary doesn't give the an. (Score:5, Funny)
Oh, so it's implied but not proven. Gotcha.
Mathematicians may read different things from the word "imply" than you do.
Re: (Score:2)
Re: (Score:2)
And it's only a theory.
Re: (Score:2)
Same thing in maths.
"P implies Q"
means "if P is true then Q is true".
Re: (Score:2)
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 l
Re: (Score:3)
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.
Re:Summary doesn't give the answer (Score:4, 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.
Re: (Score:3)
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.
Re:Summary doesn't give the answer (Score:5, 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.
Re: (Score:3)
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.
Re: (Score:1)
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.
I believe you are right, hence the distinction between NP and NP-complete in the post you replied to. I find the diagram on this page [wikipedia.org] helpful.
Re: (Score:2)
see my response. I actually pointed at the same diagram; and address your argument.
Re:Summary doesn't give the answer (Score:4, Interesting)
https://en.wikipedia.org/wiki/... [wikipedia.org]
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)
Re: (Score:3)
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, t
Re: (Score:1)
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.
Your understanding is false.
A problem is NP-hard if you can reduce all problems that are in NP to it (with a polynomial reduction). If a NP-hard problem happens to be also in NP, then the problem is (by definition) NP-complete, but nothing prevents it from being in a more difficult complexity class.
For example, the problem of satisfiability of quantified boolean formulas (QBF-SAT) is both PSPACE-complete and NP-hard. There you have a trivial reduction from the NP-complete SAT to QBF-SAT since each normal bo
Re: (Score:2)
I just checked Wikipedia and it seems you are correct. Do you know if there's a term for NP-hard problems that are not in NP but are (within the usual polynomial complexity) are the same as a problem that is in NP (and hence is NP-complete)?
Re: (Score:2)
NP-hard are not in the same class as NP-complete. NP-complete is a (fairly small) list of problems that are all equivalent to each other, within a polynomial-time conversion. NP-hard problems are not in that little group and may or may not be within NP entirely. NP-hard is kind of loosely defined as "anything harder than P that we haven't managed to otherwise classify yet."
Which means any particular NP-hard problem could be within NP-complete (and we just haven't discovered an appropriate polynomial-time
Re: (Score:1)
Is it not possible that any given problem understood to be NP might be wrongly thought to be NP, and so proving a P problem was equivalent to it would only highlight the mistaken initial categorization of the problem as being NP?
Re: (Score:2)
Is it not possible that any given problem understood to be NP might be wrongly thought to be NP, and so proving a P problem was equivalent to it would only highlight the mistaken initial categorization of the problem as being NP?
The key to answering this is in the definition of NP-complete problems.
The map coloring problem is a nice easy to understand np-complete problem. The problem is to take a map (states in a country, countries in the world, whatever, you get the idea) and a number of colors "n" and say... can I color this map with "n" different colors such that no two adjacent areas are the same color.
Basically for that problem to get into the class of "NP-complete" in the first place we have to mathematically prove two thing
Re: (Score:2)
Re: (Score:2)
Utter nonsense. All the P/NP problems are trivially solvable in finite time. The only question is the speed.
Re: (Score:1)
The state of modern, Western political discourse makes me drink heavily.
Re: (Score:3)
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.
Re: (Score:2)
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.
Re: (Score:2)
You sound preoccupied.
Re: (Score:2)
Debunk or der Bunker?
Re: (Score:2)
Re: (Score:2)
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.
Re: (Score:2)
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.
Re:Early Confirmation Bias (Score:4, Funny)
Wait, are you saying the P vs NP proof is not verifiable in polynomial time? :-)
Re: (Score:2)
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.
Re: (Score:3)
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
Re: Joke aside, why is this proof important? (Score:3)
Scroll down to consequences:
https://en.m.wikipedia.org/wik... [wikipedia.org]
Re: (Score:2)