December 17 2010

Deolalikar’s P vs NP paper

I found the internet reaction to Deolalikar’s proposed proof that P<>NP (
Deolalikar’s P vs NP paper)
fascinating. The paper is interesting in and of itself (if you like computational theory).
The massive number of notes and proof examination that the internet allowed was, to put it succinctly, really cool.

There hasn’t been much activity on this paper for quite some time. It would appear that it was a nice try, but contained several key errors. See the above link to a number of references.

Here is a link for the latest discussions on this. Essentially, there continue to be deep questions about the viability of the proof but there are many interesting areas that may be exposed.

Copyright 2020. All rights reserved.

Posted December 17, 2010 by user in category "Computation


  1. Pingback: Interesting Neutrinos « Interesting Things

Leave a Reply

Your email address will not be published. Required fields are marked *