Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
Christophe Deroulers, Rémi Monasson · Europhysics Letters (EPL) · 2004
The probability P (α, N ) that search algorithms for random satisfiability problems successfully find a solution is studied as a function of the ratio α of constraints per variable and the number N of variables. P is shown to be finite if α lies below an algorithm-dependent threshold α A , and exponentially small in N above. The critical behaviour is universal for all algorithms based on the widely used unitary propagation rule: P [(1 + )α A , N ] ∼ exp [ − N 1/6 Φ( N 1/3 )]. Exponents are related to the critical behaviour of random graphs, and the scaling function Φ is exactly calculated through a mapping onto a diffusion-and-death problem.