简述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问题。
他们之间的关系如下图所示