Pairs of SAT Assignment in Random Boolean Formulae

Abstract

We investigate geometrical properties of the random K-satisfiability problem using the notion of x-satisfiability: a formula is x-satisfiable if there exist two SAT assignments differing in Nx variables. We show the existence of a sharp threshold for this property as a function of the clause density. For large enough K, we prove that there exists a region of clause density, below the satisfiability threshold, where the landscape of Hamming distances between SAT assignments experiences a gap: pairs of SAT-assignments exist at small x, and around x=1/2, but they donot exist at intermediate values of x. This result is consistent with the clustering scenario which is at the heart of the recent heuristic analysis of satisfiability using statistical physics analysis (the cavity method), and its algorithmic counterpart (the survey propagation algorithm). The method uses elementary probabilistic arguments (first and second moment methods), and might be useful in other problems of computational and physical interest where similar phenomena appear.

References in corpus (16)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• Statistical mechanics of the random K-SAT model
• Coloring random graphs
• Survey propagation: an algorithm for satisfiability
• 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
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• The glassy phase of Gallager codes
• Polynomial iterative algorithms for coloring and analyzing random graphs
• On the dynamics of the glass transition on Bethe lattices
• The Dynamic Phase Transition for Decoding Algorithms
• On adaptability and "intermediate phase" in randomly connected networks
• Geometrical organization of solutions to random linear Boolean equations
• A frozen glass phase in the multi-index matching problem

Cited by in corpus (13)

• 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
• Finite size scaling for the core of large random hypergraphs
• Catching the k-NAESAT Threshold
• Minimal contagious sets in random regular graphs
• Entropy landscape of solutions in the binary perceptron problem
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• The large deviations of the whitening process in random constraint satisfaction problems
• Clustering of solutions in the symmetric binary perceptron
• The decimation process in random k-SAT
• Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT
• On the Solution-Space Geometry of Random Constraint Satisfaction Problems
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)