Statistical mechanics of the random K-SAT model

Details Statistical mechanics of the random K-SAT model Statistical mechanics of the random K-SAT model

1996-06-28

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

Physics

Condensed Matter

Disordered Systems and Neural Networks

34 pages + 1 table + 8 fig., submitted to Phys. Rev. E, new section added and references updated

Scientific paper

10.1103/PhysRevE.56.1357

The Random K-Satisfiability Problem, consisting in verifying the existence of an assignment of N Boolean variables that satisfy a set of M=alpha N random logical clauses containing K variables each, is studied using the replica symmetric framework of diluted disordered systems. We present an exact iterative scheme for the replica symmetric functional order parameter together for the different cases of interest K=2, K>= 3 and K>>1. The calculation of the number of solutions, which allowed us [Phys. Rev. Lett. 76, 3881 (1996)] to predict a first order jump at the threshold where the Boolean expressions become unsatisfiable with probability one, is thoroughly displayed. In the case K=2, the (rigorously known) critical value (alpha=1) of the number of clauses per Boolean variable is recovered while for K>=3 we show that the system exhibits a replica symmetry breaking transition. The annealed approximation is proven to be exact for large K.

Affiliated with

Also associated with

No associations

Rating

Statistical mechanics of the random K-SAT model 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 Statistical mechanics of the random K-SAT model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical mechanics of the random K-SAT model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-150229