Volume 68, Number 1, October 2004
|Page(s)||153 - 159|
|Section||Interdisciplinary physics and related areas of science and technology|
|Published online||01 September 2004|
Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
CNRS-Laboratoire de Physique Théorique de l'ENS 24 rue Lhomond, 75005 Paris, France
Accepted: 9 August 2004
The probability that search algorithms for random satisfiability problems successfully find a solution is studied as a function of the ratio α of constraints per variable and the number N of variables. P is shown to be finite if α lies below an algorithm-dependent threshold , and exponentially small in N above. The critical behaviour is universal for all algorithms based on the widely used unitary propagation rule: . Exponents are related to the critical behaviour of random graphs, and the scaling function Φ is exactly calculated through a mapping onto a diffusion-and-death problem.
PACS: 89.20.Ff – Computer science and technology / 05.20.-y – Classical statistical mechanics / 89.70.+c – Information theory and communication theory
© EDP Sciences, 2004
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.