P、NP、NPC、NP-Hard问题

时间:2022-05-22 22:01:33

转自:http://www.matrix67.com/blog/archives/105

总结

P:能用多项式时间求解的问题
NP:能用多项式时间验证的问题(但不知道能不能用多项式时间求解)。存在不属于NP类的问题,如:是否不存在哈密顿回路,此问题无法多项式时间验证,因为要验证所有解才能确定,而验证所有解不是多项式时间
NPC:若一个NP问题A可以以多项式时间归约(或称约化)为另一个NP问题B,则解决后者就解决了前者。归约后的问题时间复杂度是不比原问题低的(也即原问题不比归约后的难)。令人惊奇的是,所有的NP问题都可以归约为一个NP问题,而且这个NP问题还有多个,组成了一类,称为NPC问题。
NP-Hard:NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广)。NP-Hard问题同样难以找到多项式的算法,但它不列入我们的研究范围,因为它不一定是NP问题。即使NPC问题发现了多项式级的算法,NP-Hard问题有可能仍然无法得到多项式级的算法。事实上,由于NP-Hard放宽了限定条件,它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

关系

P、NP、NPC、NP-Hard问题