Instability of one-step replica-symmetry-broken phase in satisfiability problems

Abstract

We reconsider the one-step replica-symmetry-breaking (1RSB) solutions of two random combinatorial problems: k-XORSAT and k-SAT. We present a general method for establishing the stability of these solutions with respect to further steps of replica-symmetry breaking. Our approach extends the ideas of [A.Montanari and F. Ricci-Tersenghi, Eur.Phys.J. B 33, 339 (2003)] to more general combinatorial problems. It turns out that 1RSB is always unstable at sufficiently small clauses density alpha or high energy. In particular, the recent 1RSB solution to 3-SAT is unstable at zero energy for alpha< alpha_m, with alpha_m\approx 4.153. On the other hand, the SAT-UNSAT phase transition seems to be correctly described within 1RSB.

26 pages, 7 eps figures

References in corpus (4)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• The role of the Becchi-Rouet-Stora-Tyutin supersymmetry in the calculation of the complexity for the Sherrington-Kirkpatrick model

Cited by in corpus (71)

• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• A Landscape Analysis of Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• On the freezing of variables in random constraint satisfaction problems
• Focused Local Search for Random 3-Satisfiability
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Perspective: Gardner Physics in Amorphous Solids and Beyond
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Avalanches in mean-field models and the Barkhausen noise in spin-glasses
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Message passing for vertex covers
• Amorphous-amorphous transition and the two-step replica symmetry breaking phase
• Pairs of SAT Assignment in Random Boolean Formulae
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Liu-Nagel phase diagrams in infinite dimension
• Potts Glass on Random Graphs
• Minimal contagious sets in random regular graphs
• On the number of circuits in random graphs
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Cusps and shocks in the renormalized potential of glassy random manifolds: How Functional Renormalization Group and Replica Symmetry Breaking fit together
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• Diluted Mean-Field Spin-Glass Models at Criticality
• Minimizing energy below the glass thresholds
• Approximating the XY model on a random graph with a $q$-state clock model
• Glassy nature of the hard phase in inference problems
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Comparing Beliefs, Surveys and Random Walks
• Approximate Survey Propagation for Statistical Inference
• Phase transitions in the $q$-coloring of random hypergraphs
• Replica symmetry breaking in the `small world' spin glass
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• The theoretical capacity of the Parity Source Coder
• Numerical Solution-Space Analysis of Satisfiability Problems
• Cavity Method for Supersymmetry Breaking Spin Glasses
• A hard-sphere model on generalized Bethe lattices: Statics
• Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Source coding by efficient selection of ground states clusters
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Glassy phases in Random Heteropolymers with correlated sequences
• Statistical mechanics of budget-constrained auctions
• Approximating random quantum optimization problems
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Constraint optimization and landscapes
• Spin glass phase transitions in the random feedback vertex set problem
• Next nearest neighbour Ising models on random graphs
• Optimal Location of Sources in Transportation Networks
• Maximally flexible solutions of a random $K$-satisfiability formula
• Zero-Temperature Limit of the SUSY-breaking Complexity in Diluted Spin-Glass Models
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Adversarial Satisfiability Problem
• The network source location problem: ground state energy, entropy and effects of freezing
• Critical properties of disordered XY model on sparse random graphs
• Cavity approach to sphere packing in Hamming space
• The planted XY model: thermodynamics and inference
• Spanning Trees in Random Satisfiability Problems
• Survey propagation for the cascading Sourlas code
• Witness of unsatisfiability for a random 3-satisfiability formula
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
• Simplifying Random Satisfiability Problem by Removing Frustrating Interactions