|
以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 理论计算机科学 』 (http://bbs.xml.org.cn/list.asp?boardid=64) ---- 一个SAT限制问题的复杂性请教 (http://bbs.xml.org.cn/dispbbs.asp?boardid=64&rootid=&id=36559) |
|
-- 作者：ys_wang168 -- 发布时间：8/8/2006 10:08:00 PM -- 一个SAT限制问题的复杂性请教 问题: 3SAT中每个子句至少包含一个负文字,是否该3SAT是可满足的. 是NP-complete的吗?请给出证明的提示. 谢谢 |
|
-- 作者：Logician -- 发布时间：8/8/2006 10:33:00 PM -- 如果我没有理解错的话，你的意思是：给定一个合取范式，它的每一个“基本析取式”中都至少包含一个命题变元的否定形式。 如果真是这样的话，似乎：直接令所有的命题变元皆取False，则这个合取范式必然为True。从而所有符合题目要求的公式都是可满足。算法只需直接输入"TRUE"就OVER。复杂度为O(1)…… 不知道是我理解错了题目，还是哪里推错了？@_@ |
|
-- 作者：ys_wang168 -- 发布时间：8/9/2006 3:21:00 PM -- 多谢楼主! 我咋的就这么晕啊.:) |
|
-- 作者：ys_wang168 -- 发布时间：8/9/2006 3:39:00 PM -- 楼主,能帮忙证明一个复杂性问题吗?逻辑程序方面的.有意请留下email.谢谢. |
|
-- 作者：wason21cn -- 发布时间：8/14/2006 4:54:00 AM -- 如果不考虑负文字，这个问题是NP－complete的，可以用hitting set tree来解决. |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
42.969ms |