P ≠ NP ?

August 8, 2010

Daniel Martin Katz at the Computational Legal Studies Blog just posted this:

P ≠ NP ? [ Vinay Deolalikar from HP Labs Publishes His Proof to the Web, $1 Million Clay Institute Prize May Very Well Await ]

After sending his paper to several leading researchers in the field and acquiring support, Vinay Deolalikar from HP Labs has recently published P ≠ NP to the web. While it has yet to be externally verified by folks such as the Clay Mathematics Institute, it looks very promising. Indeed, this very well represent a Millennium Prize for Mr. Deolalikar. For those interested in additional information, check out Greg Baker’s blog (which broke the story). Very exciting!

This has come up once before on this blog. I’ll paste the previous entry below:

Does P=NP?

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? – Scott Aaronson (reason #9)

When you have some free time, watch this amazing lecture by Avi Wigderson about one of the great open problems in all of mathematics.

Update, 7/10 1pm: Scott Aaronson thinks there are probably good ideas in the paper, but ultimately he remains highly skeptical this is THE proof.

Advertisements

Does P=NP?

December 5, 2009

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it?  – Scott Aaronson (reason #9)

When you have some free time, watch this amazing lecture by Avi Wigderson about one of the great open problems in all of mathematics.