所有的参考来自:
What are the differences between NP, NP-Complete and NP-Hard?

决策问题: 可以用是, 或者否来回答的问题.

什么是P

多项式时间内可以求解的问题的集合.

什么是NP

表示所有决策问题的集合, 并且可以在多项式时间内验证.

什么是NPC

是NP的子类, 可以在多项式的时间内将所有的NP问题归约为NPC问题. 这个子类稍微有点特殊, 其特殊性表现在:

1. 所有的NP问题都可以在多项式时间内归约为它们;
2. 它们本身是一类NP问题;
3. 解决了这个问题, 那就意味着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.