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

CNRS-Laboratoire de Physique Théorique de l'ENS 24 rue Lhomond, 75005 Paris, France

Received: 17 May 2004
Accepted: 9 August 2004

Abstract

The probability 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 , and exponentially small in N above. The critical behaviour is universal for all algorithms based on the widely used unitary propagation rule: . 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.