J. Caleb Wherry bio photo

J. Caleb Wherry

Staff+ Software Engineer

Email Twitter Facebook LinkedIn Github Stackoverflow

I have been meaning to make this post for about 2 weeks but have not gotten around to it. I could not be silent on the issue, even if the post is a little late and lacking in actual science on my part! So, without further ado…

The scientific blogsphere (and websphere for that matter) has been in an uproar over the past few weeks with the release of a paper yielding a (potential) proof that (P \neq NP). This was released by Vinay Deolalikar, a principle research scientist at HP Labs. There has been much debate on whether this is an actual proof or just another failed attempt at proving this age old problem. The best debates can be found by Scott Aaronson: 1 & 2, Dave Bacon: 1 & 2, and Dick Lipton: 1, 2, 3, & 4.

The problem of if or if not (P = NP) has been around for quite some time. It is one of the 7 ( of the original 8 ) Clay Mathematics Millennium Problems which has a prize value of $1 Million if a proof is presented. Most theoretical computer scientists believe that (P \neq NP) and have constructed many proofs to try and show this. All of these have fallen short of their mark. Deolalikar’s proof seems to shed some new light on connecting areas that were not connected before but many believe this is as far as it goes. I leave the proving to those gifted people mentioned above in hopes that an answer to the correctness of this proof is found. Continued and updated discussions can be found on those pages above and links to other discussions as well.