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