引言
[singlepic=18468]
上图：艺术陈列馆问题（Art Gellery Problem），是一个NP-Complete问题。这里显示了一种解，四个摄像头覆盖了整个艺术陈列馆的每个角落。
P和NP就不讲了，Assert(不明白P和NP的读者不会到达这里看到这一段话)。
P是否等于NP的问题目前仍有争论，我对算法理解不深，暂时没有自己的看法。具体的讨论可以参见：WikiPedia的P=NP?讨论。不过做点猜想的话，我觉得，从数学美的角度来看，我觉得P=NP。当然，从理性思考角度来看，就像“你觉得有没有外星人”这个问题一样，理性思考的人会毫不犹豫地给出“当然有”的答案，P不应该等于NP。当然大部分计算机科学家认为P≠NP。
If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss… —— Scott Aaronson, MIT
这段话给出的启示还是很令人震惊的：任何懂得欣赏交响乐的人都可以成为莫扎特一样的音乐神童，任何懂得步步演绎问题的人都可以成为高斯一样的数学天才，因为P=NP，则说明解决问题和理解、认识和描述问题本身没有本质区别。
谈点自己的看法：Google的出现其实为我们提出了一种佐证，当你把一个问题描述清楚的时候，基本也就解决了。当你真正遇到一个问题，只要想清楚应该用什么关键字去搜索，问题的答案正在Google上等着你。
The main argument in favour of P≠NP is the total lack of fundamental progress in the area of exhaustive search. This is, in my opinion, a very weak argument. The space of algorithms is very large and we are only at the beginning of its exploration. […] The resolution of Fermat’s Last Theorem also shows that very simply [sic] questions may be settled only by very deep theories. —— Moshe Y. Vardi, Rice University
最简单的问题却要通过最复杂的理论来解决。
Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required. —— Anil Nerode, Cornell University
避免偏见，应当总是向两个方向努力。
NP-Complete问题
Cook在1971年给出并证明了有一类问题具有以下性质：
- 这类问题中任何一个问题至今未找到多项式时间算法；
- 如果这类问题中的一个问题存在有多项式时间算法，那么这类问题都有多项式时间算法（就是多项式时间内，这类问题可互相规约）。
这类问题中的每个问题称为NP完全（NP-Complete，NPC）。
NP-Hard问题
如果判定问题A满足A∈NP且NP中的任何一个问题都可在多项式时间内规约为A，则称A为NP完全（NP-Complete，NPC）。若NP中的任何一个问题都可以在多项式时间规约为判定问题A，则称A为NP难（NP-Hard，NPH）。
显然NPC⊆NPH。
NP完全和NP难问题的区别是NP难问题无需判断A是否属于NP。验证一个问题A是否为NPC的关键有两点：
- 一是NP中任何一个问题是否可在多项式时间内规约为A；
- 其次，是否存在一个字符串，其规模为实例规模的多项式函数，以及是否存在一个多项式时间的验证算法。
由于NPC里包含很多著名的组合最优化问题，经过几代数学家的努力，迄今没有找到多项式时间算法，人们猜想NPC中的任何一个问题没有多项式时间算法，即P∩NPC=∅。
这里有个图可以帮助你理解这几种问题的相互关系。可以看到，如果P=NP，数学上是比较美的。
[singlepic=18467]
一种实践方法
当然上面讲的都是理论。实践当中没有这么复杂，当你遇到一个问题，想判断这个问题是否是NPC时，只需要找一个类似的已知的NPC问题，然后想一个这两个问题之间的多项式时间转换方法即可。
这里有一个列表，包含已知的著名NP-Complete问题的列表。重要的NPC问题现在已知3000+。