Summarizing CSP hardness with continuous pro distributions
Daniel Frost, Irina Rish, Lluís Monforte · 1997
We present empirical evidence that the distribution of effort required to solve CSPs randomly generated at the 50% satisfiable point, when using a backtracking algorithm, can be approximated by two standard families of continuous probability distribution functions. Solvable problems can be modelled by the Weibull distribution, and unsolvable problems by the lognormal distribution. These distributions fit equally well over a variety of backtracking based algorithms.