P问题
如果⼀个问题能到在多项式时间内解决它的算法，那么我们说该问题是P类问题。P是多项式（Polynomial）的第⼀个字母。⽐如排序问题就是⼀个P问题，因为我们可以到⼀个时间复杂度为O(n2)O(n2)的冒泡排序算法。 NP问题
李佳霏 ⼀些问题我们很难在多项式时间内到解决问题的算法，但是如果别⼈给了我⼀个解，我可以很快地验证该解是不是问题的正确答案。⽐如在汉密尔顿回路问题中，我想验证⼀条路径是否正确，则验证路径是否正确的时间复杂度为O(n)O(n)，为多项式级的时间复杂度。
也就是说直接NP问题的⼀个解可能很慢，当验证NP问题的解却很快。
NPC问题phc桩
所有P问题都是NP问题，因为能在多项式时间内解决的问题也能够在多项式时间内验证解的正确性。
是否所有的NP问题都是P问题，这就是著名的“P对NP问题（P=NP?）”。在2000年美国的Clay数学研究所公布的七个千年数学难题中，P对NP问题位居榜⾸，可见解决该问题的难度。由于直接证明P对NP问题过于复杂，⼈们引⼊了另⼀类问题--NPC问题（NP -complete，NP-完全问题）。汇源果汁债务压顶
规约
假设有两个问题A和B，对问题A的输⼊a经过某种规则转换为对问题B的输⼊b，⽽A(a)和B(b)的结果相同，也就是说我们可以将求解A 问题转换为求解B问题，或者说可以⽤解决问题B的⽅法解决问题A，那我们称A可以归约（reducibility，或“约化”）到B。
超级NP问题
是否可以将若⼲相对不那么复杂NP问题不断归约，从⽽得到⼀个最难的“超级NP问题”，所有的NP问题都可以归约到这个“超级NP问题”，只要解决了这个“超级NP问题”，那么也就意味着所有NP问题都可以被解决。事实上，存在这样的⼀类“超级NP问题”，这也就是我们所说的NPC问题。
NPC问题的定义如下：如果⼀个问题Q，它满⾜以下两条性质：
(1). Q是NP问题
(2). 任⼀NP问题都可在多项式时间内归约到问题Q
那么我们说问题Q是NPC问题。
如果我们给NPC问题到了⼀个多项式时间复杂度的算法，那么也就意味着我们给所有的NP问题到了多项式时间复杂度的算法，从⽽NP=P，因为P=NP，所以“P对NP问题”就可以被解决。⽐如背包问题是NPC问题，如果我们给背包问题到了⼀个多项式时间复杂度的算法，那么就证明了P=NP，但给NPC问题⼀个多项式时间复杂度的算法太难了，所以现在⼈们普遍相信P≠NP。
白岩松新书
NPH问题
双指
上⾯我们介绍了NPC问题需要满⾜两条性质，当⼀个问题仅满⾜性质(2)，⽽不满⾜性质(1)时，我们说该问题时NPH问题（NP-hard，NP-难问题）。
>你在大雾里得意忘形
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议