P,NP,NP-complete,NP-hard的含义

madio

NP问题就是指其解的正确性可以在多项式时间内被检查的一类问题。比如说数组求和，得到一个解，这个解对不对呢，显然是可以在多项式时间内验证的。再比如说SAT，如果得到一个解，也是能在多项式时间内验证正确性的。所以SAT和求和等等都是NP问题。然后呢，有一部分NP问题的解已经可以在多项式时间内找到，比如数组求和，这部分问题就是NP中比较简单的一部分，被命名为P类问题。那么P以外的NP问题，就是目前还不能够在多项式时间内求解的问题了。会不会将来某一天，有大牛发明了牛算法，把这些问题都在多项式时间内解决呢？也就是说，会不会所有的NP问题，其实都是P类问题呢，只是人类尚未发现呢？NP=P吗？

7 I  W( Q5 H" g  E1 v可想而知，证明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是怎样做到的呢？

, `3 o" ~' Q8 f& Z他通过非确定性图灵机做到的。非确定性图灵机是一类特殊的图灵机，这种机器很会猜，只要问题有一个解，它就能够在多项式时间内猜到。Cook证明了，SAT总结了该机器在计算过程中必须满足的所有约束条件，任何一个NP问题在这种机器上的计算过程，都可以描述成一个SAT问题。所以，如果你能有一个解决SAT的好算法，你就能够解决非确定性图灵机的计算问题，因为NP问题在非图机上都是多项式解决的，所以你解决了SAT，就能解决所有NP，因此——SAT是一个NP完全问题。感谢Cook，我们已经有了一个NPC问题，剩下的就好办了，用归约来证明就可以了。目前人们已经发现了成千上万的NPC问题，解决一个，NP=P就得证，可以得千年大奖（我认为还能立刻获得图灵奖）。
9 |+ J; `" ^3 x! L: X0 x
7 y; @; _( x0 D6 @那么肯定有人要问了，那么NP之外，还有一些连验证解都不能多项式解决的问题呢。这部分问题，就算是NP=P，都不一定能多项式解决，被命名为NP-hard问题。NP-hard太难了，怎样找到一个完美的女朋友就是NP-hard问题。一个NP-hard问题，可以被一个NP完全问题归约到，也就是说，如果有一个NP-hard得到解决，那么所有NP也就都得到解决了。

NP-Hard和NP-Complete 区别
/ }0 w4 |1 S0 C1 [! ?
9 m- T* H3 G, L对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.

3 B2 n7 [' f$ o) k7 [/ L 让我冒着出错被人砸版砖的危险来解释一下P/NP/NP-Complete/NP-Hard。
0 e+ ~2 z7 E) f6 \6 Y$ V　　
　　1，计算复杂性
. d0 u% i4 [9 H4 c* A. k) u　　这是描述一种算法需要多少“时间”的度量。（也有空间复杂性，但因为它们能相互转换，所以通常我们就说时间复杂性。对于大小为 n 的输入，我们用含 n 的简化式子来表达。（所谓简化式子，就是忽略系数、常数，仅保留最“大”的那部分）
　　比如找出 n 个数中最大的一个，很简单，就是把第一个数和第二个比，其中大的那个再和第三个比，依次类推，总共要比 n-1 次，我们记作 O(n) (对于 n 可以是很大很大的情况下，-1可以忽略不计了）。
　　再比如从小到大排好的 n 个数，从中找出等于 x 的那个。一种方法是按着顺序从头到尾一个个找，最好情况是第一个就是 x，最坏情况是比较了 n 次直最后一个，因此最坏情况下的计算复杂度也是 O(n)。还有一种方法：先取中间那个数和 x 比较，如偏大则在前一半数中找，如偏小则在后一半数中找，每次都是取中间的那个数进行比较，则最坏情况是 lg(n)/lg2。忽略系数lg2，算法复杂度是O(lgn)。
5 d2 j* B7 J( Q# d+ f 　　
) h# x- d8 {5 w4 c; |  ~　　2，计算复杂性的排序：
! K$ u5 u( a! Q# A8 n　　根据含 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，没区别，对不？
7 y  O/ N0 H8 |7 S6 H* C! B　　
2 P% n7 N) l' C  K　　2，P 问题：对一个问题，凡是能找到计算复杂度可以表示为多项式的确定算法，这个问题就属于 P (polynomial) 问题。
7 l+ w, T! O2 y* e" e! F　　
　　3，NP 问题：
　　NP 中的 N 是指非确定的(non-deterministic）算法，这是这样一种算法：（1）猜一个答案。（2）验证这个答案是否正确。（3）只要存在某次验证，答案是正确的，则该算法得解。
+ {! s$ J" q% j$ w 　　NP (non-deterministic polynomial)问题就是指，用这样的非确定的算法，验证步骤（2）有多项式时间的计算复杂度的算法。
" C( T" t1 m' V/ C9 T$ O　　
　　4，问题的归约：
& f1 {; [  x- E- D! c　　这……我该用什么术语来解释呢？集合？太难说清了……如果你还记得函数的映射的话就比较容易想象了。
　　大致就是这样：找从问题1的所有输入到问题2的所有输入的对应，如果相应的，也能有问题2的所有输出到问题1的所有输出的对应，则若我们找到了问题2的解法，就能通过输入、输出的对应关系，得到问题1的解法。由此我们说问题1可归约到问题2。
1 V! L% m- z2 [  N 　　
( z5 X0 q- s, o- E　　5，NP-Hard：
　　有这样一种问题，所有 NP 问题都可以归约到这种问题，我们称之为 NP-hard 问题。
, C% T* s9 k. t$ F　　
7 h- ?% b! m9 T　　6，NP完全问题 (NP-Complete)：
. F4 A2 G$ i: Q% R, B2 Y　　如果一个问题既是 NP 问题又是 NP-Hard 问题，则它是 NP-Complete 问题。可满足性问题就是一个 NP 完全问题，此外著名的给图染色、哈密尔顿环、背包、货郎问题都是 NP 完全问题。
　　
# j% {2 R7 r; m0 J( Y　　从直觉上说，P<=NP<=NP-Complete<=NP-Hard，问题的难度递增。但目前只能证明 P 属于 NP，究竟 P=NP 还是 P 真包含于 NP 还未知。

空木葬花

非常感谢楼主的福利！