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:Summary doesn't give the answer

[vux984]

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.

P != NP proof

[bongey]

Paper is suggesting P!=NP .

As usual, journalists don't grok mathematicians

[MostAwesomeDude]

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

[swillden]

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

[rgmoore]

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.

I have a much, much easier proof that P != NP

[Excelcia]

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:I have a much, much easier proof that P != NP

[Anonymous Coward]

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