Board logo

标题: NP-Hard问题和NP-Complete问题 [打印本页]

作者: yuyang911220    时间: 2016-7-16 09:57     标题: NP-Hard问题和NP-Complete问题

转自:http://user.qzone.qq.com/378079686?ptlang=2052

对 NP-Hard问题和NP-Complete问题的一个直观的理解就是指那些很难(很可能是不可能)找到多项式时间算法的问题。因此一般初学算法的人都会问这样一个问题:NP-Hard和NP-Complete有什么不同?简单的回答是根据定义,如果所有NP问题都可以多项式归约到问题A,那么问题A就是 NP-Hard;如果问题A既是NP-Hard又是NP,那么它就是NP-Complete。从定义我们很容易看出,NP-Hard问题类包含了NP- Complete类。但进一步的我们会问,是否有属于NP-Hard但不属于NP-Complete的问题呢?答案是肯定的。例如停机问题,也即给出一个程序和输入,判定它的运行是否会终止。停机问题是不可判的,那它当然也不是NP问题。但对于SAT这样的NP-Complete问题,却可以多项式归约到停机问题。因为我们可以构造程序A,该程序对输入的公式穷举其变量的所有赋值,如果存在赋值使其为真,则停机,否则进入无限循环。这样,判断公式是否可满足便转化为判断以公式为输入的程序A是否停机。所以,停机问题是NP-Hard而不是NP-Complete。

NP问题就是指其解的正确性可以在多项式时间内被检查的一类问题。比如说数组求和,得到一个解,这个解对不对呢,显然是可以在多项式时间内验证的。再比如说SAT,如果得到一个解,也是能在多项式时间内验证正确性的。所以SAT和求和等等都是NP问题。然后呢,有一部分NP问题的解已经可以在多项式时间内找到,比如数组求和,这部分问题就是NP中比较简单的一部分,被命名为P类问题。那么P以外的NP问题,就是目前还不能够在多项式时间内求解的问题了。会不会将来某一天,有大牛发明了牛算法,把这些问题都在多项式时间内解决呢?也就是说,会不会所有的NP问题,其实都是P类问题呢,只是人类尚未发现呢?NP=P吗?
可想而知,证明NP=P的路途是艰难的,因为NP问题实在太多了,要一一找到多项式算法。这Stephen A. Cook这位大牛出现了,写了一篇The Complexity of Theorem Proving Procedures,提出了一个NP-complete的概念。NPC指的是NP问题中最难的一部分问题,所有的NP问题都能在多项式时间内归约到NPC上。所谓归约是指,若A归约到B,B很容易解决,则A很容易解决。显然,如果有任何一道NPC问题在多项式时间内解决了,那么所有的NP问题就都成了P类问题,NP=P就得到证明了,这极大的简化了证明过程。那么怎样证明一个问题C是NP完全问题呢?首先,要证明C是NP问题,也就是C的解的正确性容易验证;然后要证明有一个NP完全问题B,能够在多项式时间内归约到C。这就要求必须先存在至少一个NPC问题。这时Cook大牛就在1971年证明了NP完全问题的祖先就是SAT。SAT问题是指给定一个包含n个布尔变量的逻辑式,问是否存在一个取值组合,使得该式被满足。Cook证明了SAT是一个NPC问题,如果SAT容易解决,那么所有NP都容易解决。Cook是怎样做到的呢?
他通过非确定性图灵机做到的。非确定性图灵机是一类特殊的图灵机,这种机器很会猜,只要问题有一个解,它就能够在多项式时间内猜到。Cook 证明了,SAT总结了该机器在计算过程中必须满足的所有约束条件,任何一个NP问题在这种机器上的计算过程,都可以描述成一个SAT问题。所以,如果你能有一个解决SAT的好算法,你就能够解决非确定性图灵机的计算问题,因为NP问题在非图机上都是多项式解决的,所以你解决了SAT,就能解决所有NP,因此——SAT是一个NP完全问题。感谢Cook,我们已经有了一个NPC问题,剩下的就好办了,用归约来证明就可以了。目前人们已经发现了成千上万的NPC问题,解决一个,NP=P就得证,可以得千年大奖(我认为还能立刻获得图灵奖)。
那么肯定有人要问了,那么NP之外,还有一些连验证解都不能多项式解决的问题呢。这部分问题,就算是NP=P,都不一定能多项式解决,被命名为NP-hard问题。NP-hard太难了,怎样找到一个完美的女朋友就是NP- hard问题。一个NP-hard问题,可以被一个NP完全问题归约到,也就是说,如果有一个NP-hard得到解决,那么所有NP也就都得到解决了。
让我冒着出错被人砸版砖的危险来解释一下P/NP/NP-Complete/NP-Hard。

1,计算复杂性
这是描述一种算法需要多少“时间”的度量。(也有空间复杂性,但因为它们能相互转换,所以通常我们就说时间复杂性。对于大小为 n 的输入,我们用含 n 的简化式子来表达。(所谓简化式子,就是忽略系数、常数,仅保留最“大”的那部分)
比如找出 n 个数中最大的一个,很简单,就是把第一个数和第二个比,其中大的那个再和第三个比,依次类推,总共要比 n-1 次,我们记作 O(n) (对于 n 可以是很大很大的情况下,-1可以忽略不计了)。
再比如从小到大排好的 n 个数,从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找,最好情况是第一个就是 x,最坏情况是比较了 n 次直最后一个,因此最坏情况下的计算复杂度也是 O(n)。还有一种方法:先取中间那个数和 x 比较,如偏大则在前一半数中找,如偏小则在后一半数中找,每次都是取中间的那个数进行比较,则最坏情况是 lg(n)/lg2。忽略系数lg2,算法复杂度是O(lgn)。

2,计算复杂性的排序:
根据含 n 的表达式随 n 增大的增长速度,可以将它们排序:1 < lg(n) < n < nlg(n) < n^2 < ... < n^k (k是常数)< ... < 2^n。最后这个 2 的 n 次方就是级数增长了,读过棋盘上放麦粒故事的人都知道这个增长速度有多快。而之前的那些都是 n 的多项式时间的复杂度。为什么我们在这里忽略所有的系数、常数,例如 2*n^3+9*n^2 可以被简化为 n^3?用集合什么的都能解释,我忘了精确的说法了。如果你还记得微积分的话就想像一下对 (2*n^3+9*n^2)/(n^3) 求导,结果是0,没区别,对不?
2,P 问题:对一个问题,凡是能找到计算复杂度可以表示为多项式的确定算法,这个问题就属于 P (polynomial) 问题。

3,NP 问题:
NP 中的 N 是指非确定的(non-deterministic)算法,这是这样一种算法:(1)猜一个答案。(2)验证这个答案是否正确。(3)只要存在某次验证,答案是正确的,则该算法得解。
NP (non-deterministic polynomial)问题就是指,用这样的非确定的算法,验证步骤(2)有多项式时间的计算复杂度的算法。

4,问题的归约:
这……我该用什么术语来解释呢?集合?太难说清了……如果你还记得函数的映射的话就比较容易想象了。
大致就是这样:找从问题1的所有输入到问题2的所有输入的对应,如果相应的,也能有问题2的所有输出到问题1的所有输出的对应,则若我们找到了问题2的解法,就能通过输入、输出的对应关系,得到问题1的解法。由此我们说问题1可归约到问题2。


6,NP完全问题 (NP-Complete):
有这样一种问题,所有 NP 问题都可以归约到这种问题,则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题,此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。

5,NP-Hard:

从直觉上说,P<=NP<=NP-Complete<=NP-Hard,问题的难度递增。但目前只能证明 P 属于 NP,究竟 P=NP 还是 P 真包含于 NP 还未知。




欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/) Powered by Discuz! 7.0.0