Criticality and universality in the unit-propagation search rule
The probability P<Subscript>success</Subscript>(α, 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<Subscript>success</Subscript> vanishes at some critical ratio α<Subscript>H</Subscript> 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<Subscript>success</Subscript>[α<Subscript>H</Subscript> (1+epsilonN<Superscript>-1/3</Superscript>), N] ∼ A(epsilon) / N<Superscript>γ</Superscript>; the stretched exponential class, where P<Subscript>success</Subscript>[α<Subscript>H</Subscript> (1+epsilonN<Superscript>-1/3</Superscript>), N] ∼exp [-N<Superscript>1/6</Superscript> Φ(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
Year of publication: |
2006
|
---|---|
Authors: | Deroulers, C. ; Monasson, R. |
Published in: |
The European Physical Journal B - Condensed Matter and Complex Systems. - Springer. - Vol. 49.2006, 3, p. 339-369
|
Publisher: |
Springer |
Subject: | 89.20.Ff Computer science and technology | 05.40.-a Fluctuation phenomena | random processes | noise | and Brownian motion | 02.50.Ey Stochastic processes | 89.75.Da Systems obeying scaling laws |
Saved in:
Online Resource
Saved in favorites
Similar items by subject
-
Stochastic resonance in an ion channel following the non-Arrhenius gating rate
Parc, Yong Woon, (2009)
-
Constructive influence of noise-flatness in correlation ratchets
Martila, D., (2006)
-
On the structure of competitive societies
Ben-Naim, E., (2006)
- More ...