首页 > 其他 > 详细

#p-complete原来比np更难

时间:2015-02-24 16:18:09      阅读:252      评论:0      收藏:0      [点我收藏+]

转载一下豆瓣的一个不知名的朋友的介绍:

      NP是指多项式时间内验证其解是否正确。比如: 我们给一个0-1背包的解,就可以在多项式时间内验证是否满足条件。至于是否能找到 满足条件的解,这在NP复杂度里没有规定。而Sharp-P (#P)NP问题中对应的满足条件的实例或路径的个数。比如:0-1背包问有没有这样的方法让一个背包的获益大于某个参数,而负重小于一个参数;这是 NP问题。但是如果我问,有多少种方法让背包中的物品满足这个条件,那就是Sharp-P (#P)问题,我们需要首先列举出所有e为真值的可能

#p-complete原来比np更难

原文:http://www.cnblogs.com/ubiwind/p/4298733.html

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