Criticality and Universality in the Unit-Propagation Search Rule
<|reference_start|>Criticality and Universality in the Unit-Propagation Search Rule: The probability Psuccess(alpha, N) that stochastic greedy algorithms successfully solve the random SATisfiability problem is studied as a function of the ratio alpha 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, Psuccess vanishes at some critical ratio alpha\_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 Psuccess[alpha\_H (1+epsilon N^{-1/3}), N] ~ A(epsilon)/N^gamma; the stretched exponential class, where Psuccess[alpha\_H (1+epsilon N^{-1/3}), N] ~ exp[-N^{1/6} Phi(epsilon)]. Which class is selected depends on the characteristic parameters of input data. The critical exponent gamma is universal and calculated; the scaling functions A and Phi 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.<|reference_end|>
@article{deroulers2005criticality,
    title={Criticality and Universality in the Unit-Propagation Search Rule},
    author={Christophe Deroulers (LPTENS), R'emi Monasson (LPTENS)},
    journal={European Physical Journal B 49 (2006) 339-369},
    year={2005},
    doi={10.1140/epjb/e2006-00072-6},
    number={LPTENS-05/24},
    archivePrefix={arXiv},
    eprint={cond-mat/0508125},
    primaryClass={cond-mat.stat-mech cs.CC}
}