A mixture-model for the behaviour of SLS algorithms for SAT
Holger H. Hoos · 2002
Stochastic Local Search (SLS) algorithms are amongst the most effective approaches for solving hard and large propositional satisfiability (SAT) problems. Prominent and successful SLS algorithms for SAT, including many members of the WalkSAT and GSAT families of algorithms, tend to show highly regular behaviour when applied to hard SAT instances: The run-time distributions (RTDs) of these algorithms are closely approximated by exponential distributions.