简述P问题，NP问题，NP完全问题以及NP Hard问题
写在前面
在了解P问题，NP问题，NPC问题以及NP Hard问题之前，我们需要明白多项式级的复杂度和非多项式级的复杂度。时间复杂度是当问题规模扩大后，程序需要的时间长度增长得有多快。有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)。数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。
- 多项式级的复杂度，它的规模n出现在底数的位置；
- 非多项式级的复杂度，比如O(a^n)和O(n!)型复杂度，其复杂度计算机往往不能承受。
P问题
如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。
NP问题
在多项式时间内“可验证”的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。即该问题的猜测过程是不确定的，而对其某一个解的验证则能够在多项式时间内完成。P类问题属于NP问题，但NP类问题不一定属于P类问题。所有的P类问题都是NP问题，因为能多项式地解决一个问题，也就能够在多项式的时间内验证问题的解。
NP完全问题
约化： 如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。
一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A。比如一元一次方程可以约化为一元二次方程，方法为将一元二次方程的二次项系数设为0。约化具有传递性，如果问题A可以约化为问题B，问题B可以约化为问题C，则问题A可以约化为问题C。
NPC问题： 首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。
NP-Hard问题
它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。
他们之间的关系如下图所示