P、NP、NPC、NP-Hard问题科普
最近看paper时经常能看到NP问题这个字眼，然后突然想彻底弄明白它，顺便分享一下。
P问题
如果一个问题可以找到一个能在多项式的时间复杂度里解决它的算法，那么这个问题就属于P问题。
NP问题
NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题，NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。通俗地来讲，P类问题就是指那些计算机比较容易算出答案的问题；NP类问题就是指那些已知答案以后计算机可以比较容易地验证答案的问题。
NPC问题
NPC问题，又被称为NP完全问题。是指：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：
- 首先，它得是一个NP问题；
- 然后，所有的NP问题都可以约化到它。
NP-Hard问题
NP困难问题(NP-hard问题): NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条(就是说，NP-Hard问题要比NPC问题的范围广, NP-Hard问题没有限定属于NP), 即所有的NP问题都能约化到它, 但是它不一定是一个NP问题。NP-Hard问题同样难以找到多项式的算法, 但它不列入我们的研究范围, 因为它不一定是NP问题。即使NPC问题发现了多项式级的算法, NP-Hard问题有可能仍然无法得到多项式级的算法。事实上, 由于NP-Hard放宽了限定条件, 它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。
总结
