我对NP完全问题有一个体面的把握;这不是问题。我所没有的是他们在“真实”编程中出现的位置。有些人（如背包和旅行推销员）很明显，但其他人似乎并不明显与“真正的”问题有关。将NP-Complete问题与现实世界问题联系起来
我已经有几次与困难的问题挣扎的经历，只是意识到这是一个众所周知的NP完全问题已广泛研究。如果我能更快地认识到这种联系，那么我可以节省相当多的时间来研究解决具体问题的现有解决方案。
是否有任何资源（在线或打印）专门将NP Complete连接到真实世界的实例？
编辑： 例如，我正在研究一个程序，试图根据年龄，年级和学校来分组学生，这本质上是一个图分区问题。我花了一段时间才意识到这种联系。
我发现Computers and Intractability是关于此主题的权威性参考。
关于他们讨论与现实世界问题的关联程度的任何评论？它似乎很重视理论（这很好，但不是我现在要找的）。 – terru 2010-03-08 20:06:38
他们不讨论现实世界的问题，但他们有非常令人印象深刻的NP完全问题阵列，以及关于如何证明NP完全问题的一些讨论。一旦你认为你可能正在处理一个NP完全问题或NP问题，这本书是一本好书，可以查看是否有任何东西看起来很熟悉。 – 2010-03-08 20:23:27
它关注于理论。然而，它很短，如果你阅读它，它会帮助你发展那种可能是NP完全的直觉。 – 2010-03-09 02:50:36
通常你是在谈论必须以所谓减少中提取，例如连接你减少3-SAT你正在使用的问题，那么你就可以断定你的问题具有相同它的复杂性。
这段话是不平凡的，因为你必须证明你可以用把每一个问题的实例●一个已知NP难问题大号到一个实例Ç您的问题的Ç一个确定性的polinomyal算法。
因此，除了使用你的记忆学习的共同NP难问题basical的相关性，有没有办法可以肯定，如果问题类似于另一个NP难没有先试图猜测，然后证明它，你必须很聪明。
你说的一切都是正确的，但那不是我说的。例如，我正在研究一个计划，试图根据年龄，年级和学校的原因将学生分成几组，这本质上是一个图分区问题。我花了很长时间才意识到这一点。 – terru 2010-03-08 20:01:56
这里是一个维基链接： http://wapedia.mobi/en/List_of_NP-complete_problems 通知它说
这份名单是在没有办法的综合（有超过3000已知的NP完全问题）
可能会如果有人能编制这样的清单，那么这是一项伟大的任务
理论家应该尝试理解/证明NP-Complete/Hard问题。但是，程序员没有那个时间。他需要一个列表。
我正确吗？
我想你应谷歌它。并阅读所有链接。在指向您的列表的链接中添加任何新问题。
希望它可以帮助
PS：不要忘了张贴，当你完成了清单：P
为了开发更好的直觉书“的算法设计手册（第二版）”通过Skiena（谷歌书籍的摘录）简直太棒了。
阅读节选在线在这里（参见第14章举例）： http://books.google.dk/books?id=7XUSn0IKQEgC&printsec=frontcover#v=onepage&q&f=false
第16章（不在线）讨论了一些难题，包括图分区。
此外，对于难题，它提出了如何使用实际解决方案的建议。近似算法。 – 2010-11-12 23:44:05
算法设计手册还提到了一本由Garey和Johnson编写的书，其中有400个NP完整问题的评论列表。评论是我认为的很好的一部分。我没有这本书，但我正在考虑购买它。像你一样，我想要更好地理解在现实世界中认识到的难题:) 他说：只要你质疑存在问题的高效算法的存在，就浏览目录。事实上，这是我最常访问的图书馆中的一本书。 – 2010-11-12 23:47:03
http://en.wikipedia.org/wiki/List_of_np_complete_problems – kennytm 2010-03-08 19:40:00
上次我查了一下，维基百科对实际应用来说是一个不好的来源。似乎有所改善。感谢您指出。 – terru 2010-03-08 19:59:11
我同意看到NP-complete/hard问题的一些真实世界的实例，并且看到与抽象版本的连接，将会及时增加你进行连接的直觉。 – 2010-11-12 23:19:20