Towards a characterisation of the behaviour of stochastic local search algorithms for SAT

摘要

Stochastic local search (SLS) algorithms have been successfully applied to hard combinatorial problems from different domains. Due to their inherent randomness, the run-time behaviour of these algorithms is characterised by a random variable. The detailed knowledge of the run-time distribution provides important information about the behaviour of SLS algorithms. In this paper we investigate the empirical run-time distributions for WalkSAT, one of the most powerful SLS algorithms for the Propositional Satisfiability Problem (SAT). Using statistical analysis techniques, we show that on hard Random-3-SAT problems, WalkSAT's run-time behaviour can be characterised by exponential distributions. This characterisation can be generalised to various SLS algorithms for SAT and to encoded problems from other domains. This result also has a number of consequences which are of theoretical as well as practical interest. One of these is the fact that these algorithms can be easily parallelised such that optimal speedup is achieved for hard problem instances.