New worst upper bound for #SAT

Computer Science – Artificial Intelligence

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0


6 pages; proceedings of AAAI 2010

Scientific paper

The rigorous theoretical analyses of algorithms for #SAT have been proposed in the literature. As we know, previous algorithms for solving #SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving #SAT instances depends not only on the number of variables, but also on the number of clauses. Therefore, it is significant to exploit the time complexity from the other point of view, i.e. the number of clauses. In this paper, we present algorithms for solving #2-SAT and #3-SAT with rigorous complexity analyses using the number of clauses as the parameter. By analyzing the algorithms, we obtain the new worst-case upper bounds O(1.1892m) for #2-SAT and O(1.4142m) for #3-SAT, where m is the number of clauses.

No associations


Say what you really think

Search for scientists and scientific papers. Rate them and share your experience with other people.


New worst upper bound for #SAT does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New worst upper bound for #SAT, we encourage you to share that experience with our community. Your opinion is very important and New worst upper bound for #SAT will most certainly appreciate the feedback.

Rate now


Profile ID: LFWR-SCP-O-30133

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.