Relaxation and metastability in a local search procedure for the random satisfiability problem
Guilhem Semerjian, Rémi Monasson · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 2003
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 $\ensuremath{\alpha}$ of constraints per variable, reaching a solution takes a time ${T}_{\mathrm{res}}$ growing linearly $[{T}_{\mathrm{res}}\ensuremath{\sim}{\ensuremath{\tau}}_{\mathrm{res}}(\ensuremath{\alpha})N, \ensuremath{\alpha}{\ensuremath{\alpha}}_{d})$ with the size N of the instance. The relaxation time ${\ensuremath{\tau}}_{\mathrm{res}}(\ensuremath{\alpha})$ in the linear phase is calculated through a systematic expansion scheme based on a quantum formulation of the evolution operator. For $\ensuremath{\alpha}>{\ensuremath{\alpha}}_{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 $\ensuremath{\zeta}(\ensuremath{\alpha})$ of this barrier is proposed. The polynomial to exponential cross-over ${\ensuremath{\alpha}}_{d}\ensuremath{\simeq}2.7$ is not related to the onset of clustering among solutions occurring at $\ensuremath{\alpha}\ensuremath{\simeq}3.86.$