International Journal of
Physical Sciences

  • Abbreviation: Int. J. Phys. Sci.
  • Language: English
  • ISSN: 1992-1950
  • DOI: 10.5897/IJPS
  • Start Year: 2006
  • Published Articles: 2569

Full Length Research Paper

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

Zhou Junping, Ma Zhiqiang and Yin Minghao*        
School of Computer Science and Information Technology, Northeast Normal University, China.
Email: [email protected]

  •  Accepted: 20 April 2011
  •  Published: 16 September 2011

Abstract

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 variables as parameter. In this paper, an algorithm for #3-SAT with rigorous complexity analyses using the number of clauses as parameter was presented. By analyzing the algorithm, the worst-case upper bound O(1.7614m) was obtained, where m was the number of clauses.

 

Key words: Upper bound, #3-SAT, model counting, complexity analyses.

Copyright © 2024 Author(s) retain the copyright of this article.

This article is published under the terms of the Creative Commons Attribution License 4.0

Back to Vol. 6 No. 19
Back to articles
  • Articles on Google by:
SUBSCRIBE TO RSS
SUBMIT MANUSCRIPT
CONFERENCES