Charles Young
  Home  |   Contact  |   Syndication    |   Login
  184 Posts | 64 Stories | 466 Comments | 373 Trackbacks

News

MVP - Microsoft Most Valuable Professional

Twitter












Article Categories

Archives

Post Categories

Image Galleries

Alternative Feeds

BizTalk Bloggers

BizTalk Sites

CEP Bloggers

CMS Bloggers

Fun

Other Bloggers

Rules Bloggers

SharePoint Bloggers

Utilities

WF Bloggers

P ≠ NP proved?
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!

 

  • Share This Post:
  • Share on Twitter
  • Share on Facebook
  • Share on Technorati
posted on Sunday, August 29, 2010 1:14 PM

Feedback

# re: P ≠ NP proved? 8/30/2010 3:18 AM David Brabant
Mmmh. It seems that there is still room for improvement in that "proof". See various articles on:

http://rjlipton.wordpress.com/

# re: P ≠ NP proved? 8/30/2010 6:25 AM Savankumar Gudaas
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.

# re: P ≠ NP proved? 8/30/2010 8:21 PM Keith Nicholas
you can hold on to your possibility of P = NP

http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

# re: P ≠ NP proved? 8/31/2010 2:45 AM Charles Young
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.

Post A Comment
Title:
Name:
Email:
Website:
Comment:
Verification: