New Worst-Case Upper Bound for X3SAT

Details New Worst-Case Upper Bound for X3SAT New Worst-Case Upper Bound for X3SAT

2011-02-24

arxiv.org/abs/1102.4926v2

Computer Science

Artificial Intelligence

Scientific paper

The rigorous theoretical analyses of algorithms for exact 3-satisfiability (X3SAT) have been proposed in the literature. As we know, previous algorithms for solving X3SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving X3SAT 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 X3SAT 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.15855m), where m is the number of clauses.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86297