pnp
P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
NP问题是指可以在多项式的时间里验证一个解的问题。
约化：一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。
好了，从约化的定义中我们看到，若将一个问题不断约化，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。
这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC问题，也就是NP-完全问题。
如何证明一个问题是NPC问题？
- 证明它是一个NP问题
- 证明它可由另一个NPC问题约化得到（第一个NPC问题是怎么得到的？见下文）
既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。正是NPC问题的存在，使人们相信P≠NP
另一个概念NP-Hard问题：若问题A不一定属于 NP 问题，已知某一NPC 问题可在多项式时间之内转化为问题A，则称A为NP-Hard问题。