Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class

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.