Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality classC. Deroulers and R. Monasson
CNRS-Laboratoire de Physique Théorique de l'ENS 24 rue Lhomond, 75005 Paris, France
received 17 May 2004; accepted 9 August 2004
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.
89.20.Ff - Computer science and technology.
05.20.-y - Classical statistical mechanics.
89.70.+c - Information theory and communication theory.
© EDP Sciences 2004