Europhys. Lett.
Volume 68, Number 1, October 2004
Page(s) 153 - 159
Section Interdisciplinary physics and related areas of science and technology
Published online 01 September 2004
Europhys. Lett., 68 (1), pp. 153-159 (2004)
DOI: 10.1209/epl/i2004-10177-6

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

C. 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 $P(\alpha,N)$ that search algorithms for random satisfiability problems successfully find a solution is studied as a function of the ratio $\alpha$ of constraints per variable and the number N of variables. P is shown to be finite if $\alpha$ lies below an algorithm-dependent threshold $\alpha_{\ab{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+\epsilon)\alpha_{\ab{A}},N]\sim\exp[-N^{1/6}\,\Phi(\epsilon
N^{1/3})]$ . Exponents are related to the critical behaviour of random graphs, and the scaling function $\Phi$ 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