Eur. Phys. J. B 49, 339-369 (2006)
https://doi.org/10.1140/epjb/e2006-00072-6

Criticality and universality in the unit-propagation search rule^*

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

Corresponding author: ^a christophe.deroulers@lpt.ens.fr

Received: 5 August 2005
Revised: 29 November 2005
Published online: 10 March 2006

Abstract

The probability P_success(α, N) that stochastic greedy algorithms successfully solve the random SATisfiability problem is studied as a function of the ratio α of constraints per variable and the number N of variables. These algorithms assign variables according to the unit-propagation (UP) rule in presence of constraints involving a unique variable (1-clauses), to some heuristic (H) prescription otherwise. In the infinite N limit, P_success vanishes at some critical ratio α_H which depends on the heuristic H. We show that the critical behaviour is determined by the UP rule only. In the case where only constraints with 2 and 3 variables are present, we give the phase diagram and identify two universality classes: the power law class, where P_success[α_H (1+ϵN^-1/3), N] ∼ A(ϵ) / N^γ; the stretched exponential class, where P_success[α_H (1+ϵN^-1/3), N] ∼exp [-N^1/6 Φ(ϵ)]. Which class is selected depends on the characteristic parameters of input data. The critical exponent γ is universal and calculated; the scaling functions A and Φ weakly depend on the heuristic H and are obtained from the solutions of reaction-diffusion equations for 1-clauses. Computation of some non-universal corrections allows us to match numerical results with good precision. The critical behaviour for constraints with >3 variables is given. Our results are interpreted in terms of dynamical graph percolation and we argue that they should apply to more general situations where UP is used.