首页 > 代码库 > P,NP,NP_hard,NP_complete问题定义

P,NP,NP_hard,NP_complete问题定义

背景:在看李航的《统计学习方法时》提到了NP完全问题,于是摆之。

问题解答:以下是让我豁然开朗的解答的摘抄:

最简单的解释:
P:算起来很快的问题
NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对
NP-hard:比所有的NP问题都难的问题
NP-complete:满足两点:
1. 是NP hard的问题
2. 是NP问题

稍微正式的解答:

P就是能在多项式时间内解决的问题

NP就是能在多项式时间验证答案正确与否的问题。

所以P是否等于NP实质上就是在问,如果对于一个问题我能在多项式时间内验证其答案的正确性,那么我是否能在多项式时间内解决它?

NP_hard是"at least as hard as the hardest problems in NP Problem”, 就是NP-hard问题至少和NP问题一样难。

NP_complete是我能解决这个NP_hard就相当于具备了用相同级别的计算资源解决这个复杂度类里所有NP问题的能力。

比较有趣的结论是:如果我们能把NP-complete集合中的任意一个问题在多项式的时间内解决了,那么所有的NP问题都可以在多项式的时间内解决。

所以四者关系如图:

技术分享

 

参考链接:https://www.zhihu.com/question/27039635

     http://www.cnblogs.com/Gavin_Liu/archive/2011/05/04/2012284.html 

P,NP,NP_hard,NP_complete问题定义