A Comparative Runtime Analysis of Heuristic Algorithms for Satisfiability Problems

Yuren Zhou, Jun He, Qing Nie

Research output: Contribution to journalArticlepeer-review

28 Citations (SciVal)

Abstract

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.
Original languageEnglish
Pages (from-to)240-257
Number of pages18
JournalArtificial Intelligence
Volume173
Issue number2
Early online date07 Nov 2008
DOIs
Publication statusPublished - Feb 2009

Keywords

  • Boolean satisfiability
  • Heuristic algorithms
  • Random walk
  • (1+1) EA
  • Hybrid algorithm
  • Expected first hitting time
  • Runtime analysis

Fingerprint

Dive into the research topics of 'A Comparative Runtime Analysis of Heuristic Algorithms for Satisfiability Problems'. Together they form a unique fingerprint.

Cite this