Criticality and universality in the unit-propagation search rule

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+epsilonN -1/3 ), N] ∼ A(epsilon) / N γ ; the stretched exponential class, where P success [α H (1+epsilonN -1/3 ), N] ∼exp [-N 1/6 Φ(epsilon)]. 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. Copyright EDP Sciences/Società Italiana di Fisica/Springer-Verlag 2006