最坏情况下#3-SAT问题最小上界

摘要：

最坏情况下# SAT问题上界的研究已成为一个热门的研究领域.#SAT问题的时间复杂性是根据问题实例的大小所组成的函数计算所得.# SAT问题实例的大小不仅依赖于变量的数量,还依赖于子句的数量.以子句数量为参数研究# SAT问题在最坏情况下的上界,不仅可以从另一个角度衡量算法的好坏,而且在某种程度上更能准确地反映出算法的性能.首先从子句数量的角度证明了之前提出的基于扩展规则的模型计数算法(CER算法)的上界O(2m),其中,m是公式中子句的数量.为了提高#3-SAT问题的求解效率,采用了多种分裂规则,进一步给出了一种基于Davis-Putnam- LogemannLoveland (DPLL)的#3-SAT算法MCDP.通过分析该算法得到了以子句数量为参数的#3-SAT问题在最坏情况下的上界O(1.8393m).

关键词：最坏情况、上界、# 3-SAT、复杂性分析、模型计数

所属期刊栏目：48

分类号：TP301.5(计算技术、计算机技术)

资助基金：国家自然科学基金项目60673099,60773097,60803102,60873146

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2055-2063