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

In this paper we analyse the structure of the UNSAT-phase of the over-constrained 3-SAT model by studying the low temperature phase of the associated disordered spin model. We derived the full replica symmetry breaking (RSB) equations for a general class of disordered spin models which includes the Sherrington–Kirkpatrick (SK) model, the Ising p-spin model as well as the over-constrained 3-SAT model as particular cases. We have numerically solved the ∞-RSB equations using a pseudo-spectral code down to and including zero temperature. We find that the UNSAT-phase of the over-constrained 3-SAT 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 an external magnetic field.