Relaxation and metastability in a local search procedure for the random satisfiability problem

An analysis of the average properties of a local search procedure (RandomWalkSAT) for the satisfaction of random Boolean constraints is presented. Depending on the ratio α of constraints per variable, reaching a solution takes a time T_res growing linearly [T_res∼τ_res(α)N, α<α_d] or exponentially (T_res∼exp[Nζ(α)],α>α_d) with the size N of the instance. The relaxation time τ_res(α) in the linear phase is calculated through a systematic expansion scheme based on a quantum formulation of the evolution operator. For α>α_d, the system is trapped in some metastable state, and resolution occurs from escape from this state through crossing of a large barrier. An annealed calculation of the height ζ(α) of this barrier is proposed. The polynomial to exponential cross-over α_d≃2.7 is not related to the onset of clustering among solutions occurring at α≃3.86.