Relaxation and Metastability in the RandomWalkSAT search procedure

Details Relaxation and Metastability in the RandomWalkSAT search procedure Relaxation and Metastability in the RandomWalkSAT search procedure

2003-01-15

arxiv.org/abs/cond-mat/0301272v2

Phys. Rev. E 67, 066103 (2003)

Physics

Condensed Matter

23 pages, 11 figures. A mistake in sec. IV.B has been corrected

Scientific paper

10.1103/PhysRevE.67.066103

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.

Affiliated with

Also associated with

No associations

Rating

Relaxation and Metastability in the RandomWalkSAT search procedure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Relaxation and Metastability in the RandomWalkSAT search procedure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relaxation and Metastability in the RandomWalkSAT search procedure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-497747