P问题 NP问题 NPC问题 NP-Hard问题 简述
预备知识
一个问题的解决严格一样上来说，需要两步：
- 找到一个解
- 验证解的正确性
如果一个问题不能在多项式事件内得到验证的话，那么这个问题的研究价值可能不会很大
P问题
可以在多项式时间内解决的问题，或者说目前发现已经找到的可以在多项式时间内解决的问题，这些问题都都算作是P问题。
当然，我们容易想到，一个问题如果在多项式时间内找到一个解，那么也能在多项式时间内去验证这个解的正确性，所以这里的定义没有去强调“验证”，而是强调了“解决”。
大多数的NOI或者竞赛问题，都是属于P问题的，即有解。
NP问题
首先，NP问题不是 非P问题。
NP问题是指可以在多项式的时间里验证一个解的问题。
这里只是强调了验证，那么根据这个定义，P问题是属于NP问题的。但是这里有个疑问，NP问题是不是也属于P问题，或者说NP类问题中的所有问题 是不是也都是 P类问题，目前来看，大部分人认为答案是否定的。为什么还是没有结论呢？因为人们发现了NPC问题。
提出NP问题的意义是 通常只有只有NP问题，才能找到多项式的算。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。
NPC问题
NPC问题：又称NP完全问题，属于NP问题。
NPC问题需要满足一下的条件：
- 首先，它得是一个NP问题；
- 然后，所有的NP问题都可以约化到它；
NPC类问题有个特点：如果有一个NPC问题得到解决（比如在多项式时间内解决），那么所有的NP问题就能得到解决（也能在多项式时间内解决）。而这样的一类问题居然是存在的。
虽然这类问题有这么强大的特性，但是目前还没找到一个多项式时间的算法来解决其中一个NPC问题。
所以目前NPC问题的解决还是需要指数时间 或 阶乘时间的算法。
NP-Hard问题
满足NPC问题定义的第二条但不一定要满足第一条，就是说，NP-Hard问题要比 NPC问题的范围广。
NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。
事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。
参考资料
感谢大神的Blog