科学网

 找回密码
  注册
论子句消去算法的多项式时间复杂度
姜咏江 2016-10-31 10:41
论 子句消去算法的 多项式时间复杂度 姜咏江 (对外经济贸易大学 北京 中国 100013 ) 2016-10-30 摘要 本文重点论证 SAT 问题算法时间复杂度问题。文中给出了运用子句消去法求 SAT 满足解的基本方法,并对该算法的每 ...
个人分类: k-SAT求解|3079 次阅读|没有评论
子句消去法多项式时间复杂度证明的详细解释
姜咏江 2016-10-19 09:58
子句消去法 k-CNF=1 求满足解的算法如下(原文见附件): (1) 化简:将变量有唯一表现值设定为解,将相关子句消去; (2) 去掉子句块中重复子句; (3) 判断变量可选解,无可选解转( 10 ); (4) &nbs ...
个人分类: k-SAT求解|3204 次阅读|没有评论
子句消去法求k-SAT满足解的基本思路和练习
姜咏江 2016-10-18 05:27
姜咏江 子句消去法能够一次性求出 k-SAT 的满足解,基本思路十分简单。如果按照穷举法的思路,每一个逻辑变量都有 0 和 1 两个可能解值,因而 n 个变量组合到一起所成的 k-SAT 就要有 2 n 个可能解,这样就会在最坏的情况下,要验证 2 n 次才能够得到有解与无解的结果。 子句消去法的思路:假 ...
个人分类: k-SAT求解|2815 次阅读|没有评论
子句消去法求k-SAT满足解(正式发表),附件是正式版
姜咏江 2016-10-17 08:55
子句消去法求 k-SAT 满足解 姜咏江 (对外经济贸易大学 北京 中国 100013 ) (没法直接写公式,只好将2016...pdf文件放在后面。) 摘要 本文将 k-SAT 问题用表格式表达,用限位数理论和方法找出了 k-CNF 特有规律,用作者发明的变量唯一解消去法,能 ...
个人分类: k-SAT求解|3910 次阅读|没有评论
k=n时k-SAT能快速求解吗?答田文洪老师
热度 1 姜咏江 2016-6-29 12:57
k=n 时 k-SAT 能快速求解吗? 答田文洪老师 田文洪 2016-6-2821:45 姜老师,一种情况就是如同SAT问题(可把3-SAT看作其特殊组合形式),当CNF输入项是2^k个不同项时,你所建议的方法的计算复杂度。此种情况可能是SA丅问题的最坏或最难情况,应该说明一下。 博主回复(20 ...
个人分类: k-SAT求解|3994 次阅读|2 个评论 热度 1
子句消去法与子句计数法
热度 1 姜咏江 2016-1-3 09:55
子句消去法与子句计数法 姜咏江 在 3SAT 问题求解研究中,我先提出了子句消去计数法,然后又给出了子句分段消去法。后来感到前者就叫“子句计数法”,后者叫“子句消去法”更为合适。这两种 3SAT 解法之间有着怎样的关系?概括地说,子句计数法是以空间复杂度满足为基础,是获得 k-SAT 解算法时间复杂度最快速的方 ...
个人分类: k-SAT求解|3422 次阅读|4 个评论 热度 1

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-10-14 22:35

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部