A variational description of the ground state structure in random satisfiability problems

Details A variational description of the ground state structure in random satisfiability problems A variational description of the ground state structure in random satisfiability problems

1999-07-22

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

Eur. Phys. J. B 14, 551 (2000)

Physics

Condensed Matter

Disordered Systems and Neural Networks

24 pages, 6 eps figures, to be published in Europ. Phys. J. B

Scientific paper

10.1007/s100510051065

A variational approach to finite connectivity spin-glass-like models is developed and applied to describe the structure of optimal solutions in random satisfiability problems. Our variational scheme accurately reproduces the known replica symmetric results and also allows for the inclusion of replica symmetry breaking effects. For the 3-SAT problem, we find two transitions as the ratio $\alpha$ of logical clauses per Boolean variables increases. At the first one $\alpha_s \simeq 3.96$, a non-trivial organization of the solution space in geometrically separated clusters emerges. The multiplicity of these clusters as well as the typical distances between different solutions are calculated. At the second threshold $\alpha_c \simeq 4.48$, satisfying assignments disappear and a finite fraction $B_0 \simeq 0.13$ of variables are overconstrained and take the same values in all optimal (though unsatisfying) assignments. These values have to be compared to $\alpha_c \simeq 4.27, B_0 \simeq 0.4$ obtained from numerical experiments on small instances. Within the present variational approach, the SAT-UNSAT transition naturally appears as a mixture of a first and a second order transition. For the mixed $2+p$-SAT with $p<2/5$, the behavior is as expected much simpler: a unique smooth transition from SAT to UNSAT takes place at $\alpha_c=1/(1-p)$.

Affiliated with

Also associated with

No associations

Rating

A variational description of the ground state structure in random satisfiability problems 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 A variational description of the ground state structure in random satisfiability problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A variational description of the ground state structure in random satisfiability problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-286192