期刊论文详细信息
International Journal of Physical Sciences | |
The worst case upper bounds in #3-SAT with the number of clauses as the parameter | |
Zhou Junping1  | |
关键词: 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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201902015494715ZK.pdf | 64KB | download |