start | find | index | login or register | edit
2010-08-08
by earl, 3330 days ago
Vinay Deolalikar. P is not equal to NP. 6th August, 2010. "Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. The preliminary version made it to the web without my knowledge. Please note that the final version of the paper is under preparation, and is to be posted here shortly (in about a week). Stay tuned."

See also Richard Lipton's initial remarks as well as Scott Aaronson betting his house against the proof. And of course the discussion on Hacker News, Reddit/Math, Reddit/Programming, Slashdot.

Independently of whether this proof holds up or not, this is serious work spanning a wide arc across graphical models, descriptive complexity, and statistical mechanics; as such it is most likely very interesting in and of itself.

Update 2010-08-10: Lipton and Ken Regan collect possible issues with Delolikar's proof in a follow-up post.
powered by vanilla
echo earlZstrainYat|tr ZY @.
earl.strain.at • esa3 • online for 6775 days • c'est un vanilla site