Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class

Details Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class

2004-05-14

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

Europhysics Letters 68 (2004) 153-159

Physics

Condensed Matter

Statistical Mechanics

7 pages; 3 figures

Scientific paper

10.1209/epl/i2004-10177-6

The probability P(alpha, N) that search algorithms for random Satisfiability problems successfully find a solution is studied as a function of the ratio alpha of constraints per variable and the number N of variables. P is shown to be finite if alpha lies below an algorithm--dependent threshold alpha\_A, and exponentially small in N above. The critical behaviour is universal for all algorithms based on the widely-used unitary propagation rule: P[ (1 + epsilon) alpha\_A, N] ~ exp[-N^(1/6) Phi(epsilon N^(1/3)) ]. Exponents are related to the critical behaviour of random graphs, and the scaling function Phi is exactly calculated through a mapping onto a diffusion-and-death problem.

Affiliated with

Also associated with

No associations

Rating

Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class 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 Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-671209