预备知识
多项式级时间复杂度与非多项式级时间度
时间复杂度
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。
也就是说，对于某一个程序，其处理某一个特定数据的效率不能衡量该程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。
不管数据有多大，程序处理所花的时间始终是那么多的，我们就说这个程序很好，具O(1)O(1)O(1)的时间复杂度，也称常数级复杂度；
数据规模变得有多大，花的时间也跟着变得有多长，比如找n个数中的最大值这个程序的时间复杂度就是O(n)O(n)O(n)，为线性级复杂度，
而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，时间复杂度是O(n2)O(n^2)O(n2)，为平方级复杂度。
还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(an)O(a^n)O(an)的指数级复杂度，甚至O(n!)O(n!)O(n!)的阶乘级复杂度。
多项式级时间复杂度
像O(1),O(ln(n)),O(na)O(1), O(\ln(n)), O(n^a)O(1),O(ln(n)),O(na)等，我们把它叫做多项式级时间复杂度，因为它的规模n出现在底数的位置；
非多项式级时间时间度
另一种像是O(an)O(a^n)O(an)和O(n!)O(n!)O(n!)等，它是非多项式级的时间复杂度，其复杂度计算机往往不能承受。
当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
P问题与NP问题
P问题
能在多项式时间内解决的问题。
例如，计算1-1000的连续整数之和：这个问题就比较简单，无论是编程还是使用高斯求和公式都可以在有限可接受的时间内完成，这种算是P类问题。
NP问题
指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。 即能在多项式时间内验证得出一个正确解的问题。
例如，计算地球上所有原子个数之和：这个问题就很困难甚至无解，但是现在有个答案是300个，显然是错的，所以很容易验证但不容易求解，这种算NP类问题。
P问题与NP问题的关系
如果一个问题是P问题，那么毫无疑问我们可以在多项式时间内验证它。
P类问题是可以在多项式时间内解决并验证的一类问题，NP类问题是可以多项式时间验证但是不确定能否在多项式时间内解决的一类问题。
P⊆NPP \subseteq NPP⊆NP
NP-Complete(NPC)问题
这个问题需要满足两个条件:
- 它是一个NP问题
- 其他所有属于NP的问题都可以规约成它
换句话说，只要解决了这个问题，那么所有的NP问题都解决了。
可归约：就是将一个问题转化为另一个问题，使的用第二个问题的解来解第一个问题第一个问题。这种思想类似于数学证明中，如果一个证明很难从原命题切入，此时根据原命题与其逆否命题是等价的，将原命题转换成逆否命题求解，将得到及其简便的解法或者是结题的切入点。例如，假设要在一个城市中认路，如果有一张地图，就将认路问题归约得到地图问题。
同时约化还具有一个重要性质：约化具有传递性。也就是说如果问题A可约化为问题B，问题B可约化为问题C，那么问题A一定可约化为问题C。
NP-Hard问题
它满足NPC问题定义的第二条但不一定要满足第一条。 即所有的NP问题都能约化到它，但是他不一定是一个NP问题。
NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。
事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。
NPC与NP-Hard的典型示例-旅行推销员问题
旅行推销员问题（Traveling Salesman Problem, TSP） 是一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。
旅行商问题有两个版本：
- 在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问这条回路的最短路径是多少？（应如何选择行进路线，以使总的行程最短）---这个是最优解问题
- 在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问路径长度小于等于某个值的这样的回路是否存在？（应如何选择行进路线，以使总的行程小于等于某个值）---这个是判定性问题
对于问题1，是无法令确定型图灵机在多项式时间内验证答案的，所以问题1不是NP问题，因此也不是NPC问题，但是Hamilton回路问题可以约化为TSP问题，而Hamilton回路问题是NP问题，因此是NP-Hard问题。
对于问题2，可以令确定型图灵机在多项式时间内验证答案，所以问题2是NP问题，同时Hamilton回路问题可以约化为TSP问题，而Hamilton回路问题是NP问题，因此问题2是NP-Hard问题，同时它也是NPC问题。
四者之间的联系
将四种问题用集合表示，它们的关系图如下所示。
说明：
- P问题属于NP问题，NPC问题属于NP问题。
- NPC问题同时属于NP hard问题，是NP与NP hard的交集。
PS: 尚未有人能提出证明，说明NPC问题是否能在多项式时间中解决，使得此问题成为著名的数学中未解决的问题。位于剑桥市的克雷数学研究所(Clay Mathematics Institute，简称CMI)提供了一百万美金奖金给任何可以证明P=NP或P≠NP的人。
总结
说了这么多，个人认为为什么要判断一个问题是哪类问题，原因在于，它有助于让我们在决心实现这类问题之前对问题的难易程度进行一个有效的判断。如果一个问题是一个NP难问题，众所周知我们是不一定能够找到最优解的，有时候持有次优解即可（其实既然是工程问题，我们与其钻牛角尖寻求最优解，不如用小得多的代价寻求次优解）。如果一个问题连NP问题都不是，也就是说我在多项式时间内连验证它都很费劲，又谈何解决出来呢？这类问题就不大有研究的必要了。
