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

Christophe Deroulers, Rémi Monasson

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 va…