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.

Comments

Re:Mathematicians Race To Debunk

[JohnFen]

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

[serviscope_minor]

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:As usual, journalists don't grok mathematicians

[david_thornley]

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:As usual, journalists don't grok mathematicians

[gweihir]

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.