There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof.

So ... is the proof correct or not ? (Please only answer this if you have evidence ... this question might take some time until it's answered)

  • $\begingroup$ why the vote to close ? $\endgroup$ Aug 16, 2010 at 21:57
  • 7
    $\begingroup$ I think the question should specify which proof it refers to (at least mention name of the author). It is clear now, but may not be clear in a year from now. $\endgroup$
    – Moritz
    Aug 17, 2010 at 0:03
  • 2
    $\begingroup$ IMO you should address certain potential flaws in the proof. Voted to close because of the lack of specificity of the question (the quality of the posts). $\endgroup$
    – user17
    Aug 17, 2010 at 0:59
  • 2
    $\begingroup$ The link does refer to the recent story, although I'd much rather the OP link to the polymath wiki or Deolalikar's page than a slashdot post that seems less permanent $\endgroup$ Aug 17, 2010 at 3:47

3 Answers 3


In one word: No.

It seems that there are some fatal flaws in Deolalikar's proposed proof. The real question now is if the "proof" has any useful ideas that can be built upon. In any case, it seems that the proof in its current form simply isn't correct, and can't be corrected either. On the other hand, Deolalikar has not given up on the proof, so I guess it's not the end of it.

You can find an update here: http://rjlipton.wordpress.com/2010/08/15/the-p%E2%89%A0np-proof-is-one-week-old/


See the wiki.


A nice article of RL Lipton can be found in Communications of the ACM.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.