首页 > 其他 > 详细

关于P、NP、NPC和NP-Hard问题

时间:2014-12-01 22:28:43      阅读:333      评论:0      收藏:0      [点我收藏+]

1、P问题

    P中包含的是能在多项式时间内解决的问题,此类问题的时间复杂度不超过O(bubuko.com,布布扣),期中n为问题输入规模,k为常数。

2、NP问题

    NP中包含的是能在多项式时间内验证某个解是否正确的问题。

    比如:(1)所有的P问题都是NP问题,因为我们总能在多项式时间内验证给定的某个解是否正确。

               (2)对于某些不属于P问题的问题,如3-CNF可满足性问题,给出一组变量的赋值序列,我们很容易在多项式时间内验证其布尔表达式的值是否为真。

3、NPC问题

   一个问题是 NPC问题必须满足:

   (1)这个问题是NP问题;(2)所有NP问题都可以归约成它。

4、NP-Hard问题

    NP-Hard问题必须满足3中的(2),不一定满足(1)。


四者的关系可以表示如下图:(这里认为P!=NP)

bubuko.com,布布扣



关于P、NP、NPC和NP-Hard问题

原文:http://blog.csdn.net/scutwjh/article/details/41652411

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!