Criticality and universality in the unit-propagation search rule

C. Deroulers () and R. Monasson

The European Physical Journal B: Condensed Matter and Complex Systems, 2006, vol. 49, issue 3, 339-369

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+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

Keywords: 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 (search for similar items in EconPapers)
Date: 2006
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1140/epjb/e2006-00072-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurphb:v:49:y:2006:i:3:p:339-369

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/10051

DOI: 10.1140/epjb/e2006-00072-6

Access Statistics for this article

The European Physical Journal B: Condensed Matter and Complex Systems is currently edited by P. Hänggi and Angel Rubio

More articles in The European Physical Journal B: Condensed Matter and Complex Systems from Springer, EDP Sciences
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().