Clustering of solutions in the random satisfiability problem

2005/04/04 by M. Mezard, T. Mora, R. Zecchina · 17 citations
Physics and Astronomy · Computer Science · #cond-mat.dis-nn #cs.CC

paper · pdf · doi:10.1103/physrevlett.94.197205

published as Phys. Rev. Lett. 94, 197205 (2005) · 4 pages, 1 figure

arxiv created 2005/04/04 · arxiv updated 2009/12/01

Abstract

Using elementary rigorous methods we prove the existence of a clustered phase in the random K-SAT problem, for K≥ 8. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.

Cited by

• Universal energy-space localization and stable quantum phases against time-dependent perturbations
• Average-case quantum complexity from glassiness
• Are Neural Networks Collision Resistant?
• Sharp Online Hardness for Large Balanced Independent Sets
• Roadblocks and Opportunities in Quantum Algorithms -- Insights from the National Quantum Initiative Joint Algorithms Workshop, May 20--22, 2024
• Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration
• CLuP practically achieves ∼ 1.77 positive and ∼ 0.33 negative Hopfield model ground state free energy
• Beyond-mean-field fluctuations for the solution of constraint satisfaction problems
• A CLuP algorithm to practically achieve ∼ 0.76 SK--model ground state free energy
• Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT
• A large deviation view of stationarized fully lifted blirp interpolation
• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
• Phase transition of descending phase retrieval algorithms
• Overlap Gap and Computational Thresholds in the Square Wave Perceptron
• Strong Low Degree Hardness for the Number Partitioning Problem
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem

Related

• On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
• Satisfying assignments of Random Boolean CSP: Clusters and Overlaps
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT
• The cavity method: from exact solutions to algorithms