8
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ why the vote to close ? $\endgroup$ – Suresh Venkat Aug 16 '10 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 '10 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 '10 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$ – Suresh Venkat Aug 17 '10 at 3:47
20
$\begingroup$

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/

$\endgroup$
21
$\begingroup$

See the wiki.

$\endgroup$
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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