Relating NP-Complete problems to real world problems

Question

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?

Edit: For example, I was working on a program that tried to divide students into groups based on age, grade, and school of origin, which is essentially a graph partitioning problem. It took me a while to realize the connection.

Answer 1

I have found that Computers and Intractability is the definitive reference on this topic.

Answer 2

Usually the connection you are talking about must be extracted with a so-called reduction, for example you reduce 3-SAT to the problem you are working with and then you can conclude that your problem has the same complexity of it.

This passage is not trivial, since you have to prove that you can turn every problem instance l of a known NP-Hard problem L into an instance c of your problem C using a deterministic polinomyal algorithms.

So, except from learning basical correlations of common NP-Hard problems using your memory, there's no way to be sure if a problem is similar to another NP-Hard without first trying to guessing and then proving it, you have to be smart.

Answer 3

Hi, here is a wiki link: http://wapedia.mobi/en/List_of_NP-complete_problems Notice it says

This list is in no way comprehensive (there are more than 3000 known NP-complete problems)

probably it would be a great task if anyone could compile such list.

A theorist should try to understand/proof an NP-Complete/Hard problem. But, a programmer doesn't have that time to. He needs a list.

Am I correct?

I think you should google it. And, read through all the links. Add any new problem found in the link to your list.

Hope it helps

PS : Don't forget to post the list when you're finished :P