Advertisement
Published in:
2012 | OriginalPaper | Chapter
The Worst-Case Upper Bound for Exact 3-Satisfiability with the Number of Clauses as the Parameter
Authors : Junping Zhou, Minghao Yin
Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.15855
m
), where
m
is the number of clauses.