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.
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.
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 .
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?
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.
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.
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.
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.
We need a new elegantly caustic mod category just to be fair with your comment. LOL.
Custom Solvers 2.0 = Alvaro Carballo Garcia = varocarbas.
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.
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.
Firstly, I couldn't understand why anyone would have bought such a domain name. Now, I completely get it and my life has finally a purpose! LOL.
Custom Solvers 2.0 = Alvaro Carballo Garcia = varocarbas.
I guess he created meta N = NP problem.
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 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 helpful.
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 /.
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)
Debunk or der Bunker?
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
see my response. I actually pointed at the same diagram; and address your argument.
Scroll down to consequences:
https://en.m.wikipedia.org/wik...
"So long and thanks for all the fish."
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
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.
Oh yeah? Prove it.
<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]
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.
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.
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 boolean formula is also a QBF-formula that just happens to have no quantifiers.
In short: hardness gives only the lower bound of complexity, while completeness gives both the lower and the upper bound.
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"
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
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?
tone
For those who haven't heard, there's a pretty good movie about this: Travelling Salesman (2012), required viewing for math geeks.
Non-Linux Penguins ?
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)?
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
Utter nonsense. All the P/NP problems are trivially solvable in finite time. The only question is the speed.
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 things:
a) a proposed solution can be verified in polynomial time. In this case that means if I give you a list of all the areas of the map each with one of the n colors assigned to it, how long will it take you to verify that it is a valid solution? In this case, you can simply look at each area on the map, note its color, and then check that none of its neighbors are the same color. That's got a time complexity on the number of areas squared. So that's easy to check in polynomial time.
b) can all other NP-complete problems be reduced to this one. In practice, once you show one can be reduced to this problem, that shows they all are because all the others have been shown to reduce to the one you looked at, and the transformations can be stacked up in polytime to inductively prove the whole class reduces to this problem. (So if it takes o^5 to reduce B to A, and o^3 to reduce C to B then it's not going to be any worse than O^8 to reduce C to A, and that's still polytime. The upshot is that you only need to find one mapping, but even so, this is a LOT more complicated to show, and I won't get into it here. The transformation is simply a 'mechanical' process so once you come up a transformation you can automate it.
Thus the transformation needs to show how you can take a DIFFERENT NP-Complete problem, mechanically transform it to this one, and then use the solution to this one, to identify a solution to the other one.
Now, going back to your question. If a given problem is "understood to be NP complete" - and you find a P solution for it, then
a) Either the accepted proof that it was was NP-complete was wrong. (unlikely but possible); and you move that one problem into P
b) Or the solution you found does solve the problem, and then in turn DOES solve the other NP-complete problems, and you have just proven P=NP.
So, yeah, its possible a problem was miscategorized, but its not at all likely because both the solution verification, and the mechanical transformation parts of NP-complete proofs can be mechanically implemented and tested. So while there is a bit of cleverness in coming up with the transformation, if it was flawed, it wouldn't actually *work*. So its unlikely it would go undetected. Plus its even more unlikely because most of the graph problems are easily related to eachother, and most of the SAT problems are like wise easily related to eachother and the proofs are simple enough. Their are multiple proofs relating SAT problems to graph problems, etc... so the odds of an accepted NP-complete proof being wrong is further reduced because there are multiple such proofs relating different problems creating a network or web of proofs.
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.
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 conversion) or they could be outside of NP completely but again we just haven't managed to conclusively prove it.
TSP is a bit special in that there's two variants -- the decision variant ("does a path exist yes/no?") is NP-complete, but actually finding the path is NP-hard.
Showing that P=NP would immediately reduce everything in NP-complete to polynomial time (how to do that is not necessarily part of the statement unfortunately) but it wouldn't necessarily imply all NP-hard problems could be reduced to polynomial time due to the looseness of the definition (that is, some problems labeled NP-hard may not be NP at all and the P=NP proof wouldn't apply to them.. though it could potentially be used for contradiction to show certain problems are definitively not NP and could be properly categorized outside of NP-hard.)