所有的参考来自:
What are the differences between NP, NP-Complete and NP-Hard?
决策问题: 可以用是, 或者否来回答的问题.
什么是P
多项式时间内可以求解的问题的集合.
什么是NP
表示所有决策问题的集合, 并且可以在多项式时间内验证.
什么是NPC
是NP的子类, 可以在多项式的时间内将所有的NP问题归约为NPC问题. 这个子类稍微有点特殊, 其特殊性表现在:
- 所有的NP问题都可以在多项式时间内归约为它们;
- 它们本身是一类NP问题;
- 解决了这个问题, 那就意味着NP问题都可以得到解决了.
可以这样理解NPC问题是NP问题的典型, 解决了它们, NP问题就解决了.(要抓就抓典型)
什么是NP难(NP-Hard)
直观的说, 这些问题至少和np问题一样困难(困难程度: NP难 >= NP).
精确的定义X是NP难问题, NPC问题Y可以在多项式时间内归约为X. (这里的X, 不一定是NP问题, 如果X==NP, 那么NP难就是NPC了)
也就是说, 只要在多项式时间内解决了一个NP难问题, 那么所有的NPC问题都可以在多项式时间内解决了, 那么也就是说所有的NP问题都可以在多项式时间内解决了.
需要注意的是, NP难问题不一定是 NP 问题, 而且它们不一定是决策问题.
p, np, npc, np难关系图
还有一个表帮助理解:(难度从上倒下, 依次增大)
| 问题类型 | P时间内可验证 | P时间内可以求解 |
|---|---|---|
| P | Yes | Yes |
| NP | Yes | Yes or No * |
| NPC | Yes | Unknown |
| NP难 | Yes or No ** | Unknown *** |
注解:
* 当一个P问题的NP问题, 可以在P的时间内解决. (因为P是NP的子集)
** 当一个NP难问题是一个NPC问题的时候, 可以在P时间内验证
*** NP-Complete problems (all of which form a subset of NP-hard) might be. The rest of NP hard is not.
