Geeks With Blogs

News
Oh my. Somehow I missed this one from earlier this month.   A guy from HP Labs called Vinay Deolalikar claims he has the proof. P ≠ NP. I'm nowhere near clever enough to follow his arguments (see http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf for a synopsis), but I understand the impact.
If he is right, then in a sense, nothing changes. It's just that we will now know for sure that there is no magic formula that will revolutionise the efficiency of our software.   The proof will confirm what has been long suspected. However, if the proof holds up, then it is a major milestone in computer science. I mean MAJOR.
Nothing personal against Mr Deolalikar, but I really hope the proof does not hold up. The idea that P could just possibly equal NP is so beguiling.
No idea what I am talking about? Here comes Wikipedia to the rescue!   http://en.wikipedia.org/wiki/P_%3D_NP_problem
And here is a really easily digestible explanation from the good ol’ BBC. Jigsaws work for me!

Comments on this post: P ≠ NP proved?

# re: P ≠ NP proved?
Mmmh. It seems that there is still room for improvement in that "proof". See various articles on:

http://rjlipton.wordpress.com/
Left by David Brabant on Aug 30, 2010 3:18 AM

# re: P ≠ NP proved?
I attended a seminor in University of Hyderabad of Prof N.S.Chowdary from IIT Indor . Who working on P=NP from last 4 years finally now he has a proof of P=NP and he presented first time in our University of Hyderabad.
He showed the proof and if every thing is fine then it will be a break through in CS and Artificial intelligence.
Left by Savankumar Gudaas on Aug 30, 2010 6:25 AM

# re: P ≠ NP proved?
you can hold on to your possibility of P = NP

http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/
Left by Keith Nicholas on Aug 30, 2010 8:21 PM