Skip to content

Definitive Word on P!=NP Paper

Lance Fortnow of the blog Computational Complexity has, I believe, the definitive word on the P!=NP paper by Deolalikar (saying in a sentence what I couldn’t quite manage in two pages):

Proving P  ≠ NP will require pure genius but you shouldn’t need a Fields medalist to verify the proof.

Secondary message:  a good way to determine if a proof will work is to count the “clearly”s and “should be able to”s:  more than one or two and the proof likely will fall apart at the slightest breath.

{ 1 } Comments

  1. Paul Rubin | September 7, 2010 at 2:35 pm | Permalink

    I agree with your secondary message, although I would opt to preclude “should be able to” entirely. As far as Fortnow’s contention, though, I’m not sure I buy into it. He cites two major results where an undergraduate math major (allegedly) could verify the arguments. That’s great, and more power to the authors, but I’m pretty sure that description would not apply to Wiles’s (second, correct) proof of Fermat’s Last Theorem. So was Wiles wrong?

Share Your Views!

Your email is never published nor shared. Please do not enter non-operations research websites: just leave blank if not OR. COMMENTS WITH NON-OR WEBSITES WILL BE MARKED AS SPAM AND DELETED! Required fields are marked *