## P vs NP finally resolved?

A new paper has appeared from Vinay Deolalikar in HP Labs claiming to prove P is not equal to NP (in fact P≠NP is the title). Normally I ignore the constant stream of papers on the subject, but this work looks like a serious attempt and is being taken seriously by a number of people I respect, so it has jumped straight to the top of my reading list.

For more details see posts by the Pontiff, Greg Baker, and R J Lipton.

I really hadn’t expected to see this proved within my life time, so I am of course skeptical. Still, even if there is an error, perhaps it opens up a new approach.

August 10th, 2010 at 6:07 am

[…] the constant stream of papers on the subject, but this work looks like a serious attempt …This Blog Chargement […]

August 10th, 2010 at 6:14 am

[…] Joe Fitzsimons […]

August 20th, 2010 at 6:00 pm

[…] The rest is here: Quantized Thoughts » Blog Archive » P vs NP finally resolved? […]

September 6th, 2010 at 11:05 am

[…] Joe Fitzsimons Buzz: A new paper has appeared from Vinay Deolalikar in HP Labs claiming to prove P is not equal to NP (in fact P≠NP is the title). Normally I ignore the constant stream of papers on the subject, but this work looks like a … […]