Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
<|reference_start|>Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class: 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.<|reference_end|>
@article{deroulers2004critical,
    title={Critical behaviour of combinatorial search algorithms, and the
  unitary-propagation universality class},
    author={Christophe Deroulers (LPTENS), R'emi Monasson (LPTENS)},
    journal={Europhysics Letters 68 (2004) 153-159},
    year={2004},
    doi={10.1209/epl/i2004-10177-6},
    number={preprint LPTENS 04/25},
    archivePrefix={arXiv},
    eprint={cond-mat/0405319},
    primaryClass={cond-mat.stat-mech cs.CC}
}