首页 > 代码库 > 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问题定义
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。