The 3-SAT problem with large number of clauses in ∞-replica symmetry breaking scheme

Original · EN

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 ∞ 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 ∞ 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 ∞-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.