整理一下。肯定有错误之处,请高手指正。 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也就都得到解决了。 NP-Hard和NP-Complete 区别 对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. 让我冒着出错被人砸版砖的危险来解释一下P/NP/NP-Complete/NP-Hard。 |
|