The worst case upper bounds in #3-SAT with the number of clauses as the parameter

International Journal of Physical Sciences

Zhou Junping¹ 

关键词: Upper bound;    #3-SAT;    model counting;    complexity analyses.;   

DOI  :  10.5897/IJPS11.442

学科分类：物理（综合）

来源: Academic Journals

【 摘 要 】

The rigorous theoretical analyses of algorithms for #SAT problem had been proposed in recent years. However, as far as we know, all algorithms for solving #SAT had been analyzed using the number of variablesas parameter. In this paper, an algorithm for #3-SAT with rigorous complexity analyses using the number of clausesas parameter was presented. By analyzing the algorithm, the worst-case upper boundO(1.7614m) was obtained, wheremwas the number of clauses.

【 授权许可】

CC BY