Relaxation and Metastability in the RandomWalkSAT search procedure
<|reference_start|>Relaxation and Metastability in the RandomWalkSAT search procedure: An analysis of the average properties of a local search resolution procedure for the satisfaction of random Boolean constraints is presented. Depending on the ratio alpha of constraints per variable, resolution takes a time T_res growing linearly (T_res \sim tau(alpha) N, alpha < alpha_d) or exponentially (T_res \sim exp(N zeta(alpha)), alpha > alpha_d) with the size N of the instance. The relaxation time tau(alpha) 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(alpha) of this barrier is proposed. The polynomial/exponentiel cross-over alpha_d is not related to the onset of clustering among solutions.<|reference_end|>
@article{semerjian2003relaxation,
    title={Relaxation and Metastability in the RandomWalkSAT search procedure},
    author={Guilhem Semerjian, Remi Monasson},
    journal={Phys. Rev. E 67, 066103 (2003)},
    year={2003},
    doi={10.1103/PhysRevE.67.066103},
    number={LPT-ENS 02/66},
    archivePrefix={arXiv},
    eprint={cond-mat/0301272},
    primaryClass={cond-mat cs.CC}
}