Relating NP-Complete problems to real world problems

Posted by terru on Stack Overflow See other posts from Stack Overflow or by terru
Published on 2010-03-08T19:37:12Z Indexed on 2010/03/08 19:51 UTC
Read the original article Hit count: 510

Filed under:

online-resources

I have a decent grasp of NP Complete problems; that's not the issue. What I don't have is a good sense of where they turn up in "real" programming. Some (like knapsack and traveling salesman) are obvious, but others don't seem obviously connected to "real" problems.

I've had the experience several times of struggling with a difficult problem only to realize it is a well known NP Complete problem that has been researched extensively. If I had recognized the connection more quickly I could have saved quite a bit of time researching existing solutions to my specific problem.

Are there any resources (online or print) that specifically connect NP Complete to real world instances?

Related posts about online-resources

delphi prism online resources

as seen on Stack Overflow - Search for 'Stack Overflow'
google search on ''delphi prism' , ''delphi prism resources'' or ''delphi prism code snippets'' reveal almost no good site at all are there any good programming site(s) with some good amount of code snippets and tutorials on delphi prism thanks in advance >>> More
books or online resources to prepare for .NET interviews for senior developer role

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, can you suggest some good books or online resources (FAQ or articles) to prepare for .NET interviews (.NET concepts, ASP.NET, C# etc) for senior developer role? something to refresh the concepts, not too much detailed. there could be stuff I haven't done before (that applies to everyone), so at… >>> More
Google adwords API - credit card safety question

as seen on Pro Webmasters - Search for 'Pro Webmasters'
Hi, Google is asking me to fax credit card xerox in order to activate adwords API in MCC. This really sucks imo... they could have had prepaid option. In any case, my questions: 1) Are there alternatives to this - is there a 3rd party provider who will give me this service without me sending them… >>> More
Modern monitor technologies - need to find a new monitor

as seen on Super User - Search for 'Super User'
I'm preparing to change my old LCD monitor for a new one. I have an old NEC 20WGX2 Pro based on an IPS panel. I'm looking for a screen that gives good color output but is very good at gaming at the same time (since it is its primary service). I tend to switch monitors between my different computers… >>> More
Paid service that will bulk convert HTML and text to PDF?

as seen on Super User - Search for 'Super User'
We have a repository of documents in HTML and text that we're looking to get into PDF format, but my boss (another developer) feels that writing this portion of the application will detract from the main development that we're doing at the moment. Is anyone aware of any services that will be able… >>> More

Developer IT