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 $\alpha$ of constraints per variable, reaching a solution takes a time $T_{\mathrm{res}}$ growing linearly $\left[T_{\mathrm{res}}\sim {\tau }_{\mathrm{res}}\right(\alpha )N,\hspace{0.5em}\alpha <{\alpha }_d]$ or exponentially $\left(T_{\mathrm{res}}\sim \exp \right[N\zeta \left(\alpha \right)],\alpha >{\alpha }_d)$ with the size N of the instance. The relaxation time ${\tau }_{\mathrm{res}}\left(\alpha \right)$ in the linear phase is calculated through a systematic expansion scheme based on a quantum formulation of the evolution operator. For $\alpha >{\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 $\zeta \left(\alpha \right)$ of this barrier is proposed. The polynomial to exponential cross-over ${\alpha }_d\simeq 2.7$ is not related to the onset of clustering among solutions occurring at $\alpha \simeq \mathrm{3.86.}$