*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

** 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.

**PACS**

89.20.Ff - Computer science and technology.

05.20.-y - Classical statistical mechanics.

89.70.+c - Information theory and communication theory.

**©**

*EDP Sciences 2004*