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.


0 Comments:
Post a Comment
<< Home