New Worst-Case Upper Bound for #XSAT

Details New Worst-Case Upper Bound for #XSAT New Worst-Case Upper Bound for #XSAT

2011-02-24

arxiv.org/abs/1102.4924v1

Computer Science

Artificial Intelligence

submitted to AAAI-10

Scientific paper

An algorithm running in O(1.1995n) is presented for counting models for exact satisfiability formulae(#XSAT). This is faster than the previously best algorithm which runs in O(1.2190n). In order to improve the efficiency of the algorithm, a new principle, i.e. the common literals principle, is addressed to simplify formulae. This allows us to eliminate more common literals. In addition, we firstly inject the resolution principles into solving #XSAT problem, and therefore this further improves the efficiency of the algorithm.

Affiliated with

Also associated with

No associations

Rating

New Worst-Case Upper Bound for #XSAT 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-Case Upper Bound for #XSAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Worst-Case Upper Bound for #XSAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86290