|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- 也许你的一句话就能为我指点迷津==关于npcomplet的问题 (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=40435) |
|
-- 作者：petitmiracle -- 发布时间：11/23/2006 5:32:00 PM -- 也许你的一句话就能为我指点迷津==关于npcomplet的问题 困扰我的一个问题，如果想证明一个问题是np完全问题，那么只要找到已知的一个npcomplet问题，将其规约到想要证明的问题上。比如已知sat是npcomplet问题，将其规约到3sat上就可以证明3sat是npcomplet,但是我的理解是3sat是属于sat的，怎么可以将一个普遍的问题规约到一个子问题上呢？ 可能是个弱智问题，但也许你的一句话可以指点迷津。 |
|
-- 作者：Logician -- 发布时间：11/24/2006 5:51:00 AM -- 为什么不可以将一个普遍的问题规约到一个子集上呢（顺便说一下，这里用“子问题”似乎不合适，“A是B的子问题”通常指“解决问题B需要分若干步，其中的一步是解决问题A”，这里说“3SAT是SAT的一个子集”似乎更妥当些）？ 举一个也许不太恰当的例子：解一元二次不等式的问题可以规约到解“Ax^2 + Bx + C ≤ 0”这类标准形式的的问题上来。而具有“Ax^2 + Bx + C ≤ 0”这一标准形式的一元二次不等式只是“所有一元二次不等式”的一个子集。这就是普遍问题规约到它的一个子集上的例子。 A规约到B，就是说“找到一种‘化归’的方法”，使得把每一个A类问题都能统一地“化归”到某个B类问题上去，找到B类问题的解之后，就反过来知道了A类问题的解。从这个意义上去理解“规约”的话，就很容易理解为什么一类问题可以规约到它的一个子集上去了。 |
|
-- 作者：petitmiracle -- 发布时间：11/25/2006 3:39:00 AM -- 真是万分感谢你的回复,我似乎明白了.通过你的解释,我的理解是:规约的目的就是解决问题,我们所能解决的问题大部分都是"特殊"的问题(一个普遍问题的一个子集),如果能找到"划归"的方法,那么我们就找到了普遍问题的解法.规约的重点和难点在于找到这个"划归的方法",和网什么问题上划归...是吗?再次感谢你的回复,一直担心着没人回复呢:)
|
|
-- 作者：Logician -- 发布时间：11/27/2006 3:58:00 PM -- 对，就是这样。：） |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
59.082ms |