Well, it happens every now and then, that someone finds a proof for a long standing theoretical problem.

This time it’s the famous P = NP or P != NP problem of computer science that Gecko pointed me to:

- P != NP, the proof (yet to be accepted) (Updated on Aug. 10th)
- Index page, seems there were some updates (added on Aug. 11th)
- (Another mirror)
- Vinay Deolalikar in Wikipedia (as always Wikipedia folks want to delete ;))
- Slashdot
- Heise News (thx Simon) (added on Aug. 9th)

Let’s wish him luck that his proof is flawless and accepted.

(Who’s the first one to say: “I’ve always known it” ? :D)

- First summary of some issues (added on Aug. 10th)
- A List of other attempts to solve PNP (thx Harald) (added on Aug. 11th)
- Bruce Schneier bets the proof is flawed 😉 (added on Aug. 11th)
- Easy xkcd explanation of NP-Completeness (added on Aug. 11th)
- Wikipedia on P versus NP with ref to fatal flaws of Deolalikars proof. (added on Aug. 20th)

Sadly my wishes didn’t help :-/

RaphaelWhat a pity 🙁

Having only read the synopsis, I remain sceptical. We will see what his peers have to say about it.

On page 7, “Now we close the loop and […]” caused me to snicker maliciously. Bad me.

joernPost authorAs a partly funny, partly serious side-note, read this:

http://www.scottaaronson.com/blog/?p=304 (thanks Damian 😉 )

RaphaelNow I know what bugged me 😀

DominikFor the serious part of your side-note, could you enlighten us which of these ten points apply in your opinion?

joernPost authorI think the paper passed the 10 tests and currently is in this phase:

“At some point, there might be nothing left to do except to roll up your sleeves, brew some coffee, and tell your graduate student to read the paper and report back to you.” 😉

Nevertheless I think the list is a serious first filter heuristic for people who—unlike me—have to rate a lot solution attempts for big theoretical problems.

haraldWow…the internet allows for fast review cycles 😉 There’s already a list of potential issues with the proof – quite impressive considering the length of the paper and the short time since its “publication” on monday.

http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E2%89%A0np/

ArchiWell, as long as he does not “proof” that p==np, we won’t be in much trouble 😉

Anyway, it is good to see people working on that problem, and maybe we – even if the proof is faulty – maybe we get closer to the solution of this important question.

But what is if he is right? What will be the next “well known” big problem in that research field? ;-)l

haraldAnother interesting read regarding P vs. NP proofs:

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

(P=NP wins the proof battle with approx. 30/59 😉 )

joernPost authorThanks, indeed a nice link… added it.