Criticality and Universality in the Unit-Propagation Search Rule

Details Criticality and Universality in the Unit-Propagation Search Rule Criticality and Universality in the Unit-Propagation Search Rule

2005-08-04

arxiv.org/abs/cond-mat/0508125v2

European Physical Journal B 49 (2006) 339-369

Physics

Condensed Matter

Statistical Mechanics

30 pages, 13 figures

Scientific paper

10.1140/epjb/e2006-00072-6

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.

Affiliated with

Also associated with

No associations

Rating

Criticality and Universality in the Unit-Propagation Search Rule does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Criticality and Universality in the Unit-Propagation Search Rule, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Criticality and Universality in the Unit-Propagation Search Rule will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-614089