P ≠ NP proved?

<< IE9 Chrome | Home | I'm a PC, and I love IE. >>

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!

http://www.bbc.co.uk/news/science-environment-10938302?utm_source=SamacharNepal&utm_medium=SamacharNepal.

Posted on Sunday, August 29, 2010 1:14 PM | Back to top

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

# re: P ≠ NP proved?

Yes, I saw Dick Lipton's response. As I understand it, Vinay Deolalikar has made some amendments to his paper which are currently being reviewed. We shall have to wait to see what the verdict is.

Left by Charles Young on Aug 31, 2010 2:45 AM

Your comment:

Title:

Name:

Email: (never displayed) (will show your gravatar)

Comment: Allowed tags: blockquote, a, strong, em, p, u, strike, super, sub, code

Verification: