TY - JOUR
T1 - A Comparative Runtime Analysis of Heuristic Algorithms for Satisfiability Problems
AU - Zhou, Yuren
AU - He, Jun
AU - Nie, Qing
N1 - Zhou, Y., He, J., Nie, Q. (2009). A Comparative Runtime Analysis of Heuristic Algorithms for Satisfiability Problems. Artificial Intelligence, 173 (2), 240-257
PY - 2009/2
Y1 - 2009/2
N2 - The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, (1+1) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary k-SAT (kgreater-or-equal, slanted3) is O((k−1)n), and presents a k-SAT instance that has Θ((k−1)n) expected runtime bound.
AB - The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, (1+1) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary k-SAT (kgreater-or-equal, slanted3) is O((k−1)n), and presents a k-SAT instance that has Θ((k−1)n) expected runtime bound.
KW - Boolean satisfiability
KW - Heuristic algorithms
KW - Random walk
KW - (1+1) EA
KW - Hybrid algorithm
KW - Expected first hitting time
KW - Runtime analysis
U2 - 10.1016/j.artint.2008.11.002
DO - 10.1016/j.artint.2008.11.002
M3 - Article
SN - 0004-3702
VL - 173
SP - 240
EP - 257
JO - Artificial Intelligence
JF - Artificial Intelligence
IS - 2
ER -