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

Abstract

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.

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

References in corpus (1)

• Exact solutions for diluted spin glasses and optimization problems

Cited by in corpus (22)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• The glass transition and the Coulomb gap in electron glasses
• Analysis of the infinity-replica symmetry breaking solution of the Sherrington-Kirkpatrick model
• The spherical 2+p spin glass model: an analytically solvable model with a glass-to-glass transition
• The spherical $2+p$ spin glass model: an exactly solvable model for glass to spin-glass transition
• Potts Glass on Random Graphs
• Thermodynamic Properties and Phase Transitions in a Mean-Field Ising Spin Glass on Lattice Gas: the Random Blume-Emery-Griffiths-Capel Model
• First Order Phase Transition and Phase Coexistence in a Spin-Glass Model
• Quenched Computation of the Complexity of the Sherrington-Kirkpatrick Model
• Phase transitions in the $q$-coloring of random hypergraphs
• Universality class of replica symmetry breaking, scaling behavior, and the low-temperature fixed-point order function of the Sherrington-Kirkpatrick model
• On Equilibrium Dynamics of Spin-Glass Systems
• Full replica symmetry breaking in generalized mean--field spin glasses with reflection symmetry
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Fermionic SK-models with Hubbard interaction: Magnetism and electronic structure
• How to refute a random CSP
• Strongly Refuting Random CSPs Below the Spectral Threshold
• Low temperature spin glass fluctuations: expanding around a spherical approximation
• Lower bounds for CSP refutation by SDP hierarchies
• Breaking of 1RSB in random MAX-NAE-SAT
• Phase transitions in integer linear problems