The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme

Details The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme

2001-08-27

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

J. Phys. A: Math. Gen. 35, 481-497 (2002)

Physics

Condensed Matter

Statistical Mechanics

19 pages, 7 figures; some section improved; iopart style

Scientific paper

10.1088/0305-4470/35/3/303

In this paper we analyze the structure of the UNSAT-phase of the overconstrained 3-SAT model by studying the low temperature phase of the associated disordered spin model. We derive the $\infty$ Replica Symmetry Broken equations for a general class of disordered spin models which includes the Sherrington - Kirkpatrick model, the Ising $p$-spin model as well as the overconstrained 3-SAT model as particular cases. We have numerically solved the $\infty$ Replica Symmetry Broken equations using a pseudo-spectral code down to and including zero temperature. We find that the UNSAT-phase of the overconstrained 3-SAT model is of the $\infty$-RSB kind: in order to get a stable solution the replica symmetry has to be broken in a continuous way, similarly to the SK model in external magnetic field.

Affiliated with

Also associated with

No associations

Rating

The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme 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 The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-113108