Title: On the run-time behaviour of stochastic local search algorithms for SAT
Abstract: Stochastic local search (SLS) algorithms for the propositional satisfiability problem (SAT) have been successfully applied to solve suitably encoded search problems from various domains. One drawback of these algorithms is that they are usually incomplete. We refine the notion of incompleteness for stochastic decision algorithms by introducing the notion of probabilistic asymptotic completeness (PAC) and prove for a number of well-known SLS algorithms whether or not they have this property. We also give evidence for the practical impact of the PAC property and show how to achieve the PAC property and significantly improved performance in practice for some of the most powerful SLS algorithms for SAT, using a simple and general technique called random walk extension.
Publication Year: 1999
Publication Date: 1999-07-18
Language: en
Type: article
Access and Citation
Cited By Count: 165
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot