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.

4 Responses to “P vs NP finally resolved?”

  1. decencyisarelativething » Quantized Thoughts Blog Archive P Vs Np Finally Resolved? Says:

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

  2. P≠NP. at webCONSUL Says:

    […] Joe Fitzsimons […]

  3. Quantized Thoughts » Blog Archive » P vs NP finally resolved? < Read what Young Americans Read Says:

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

  4. vinay deolalikar | WebBuzz Says:

    […] 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 … […]

Leave a Reply