From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy

Abstract

A solution to a 3-satisfiability (3-SAT) formula can be expanded into a cluster, all other solutions of which are reachable from this one through a sequence of single-spin flips. Some variables in the solution cluster are frozen to the same spin values by one of two different mechanisms: frozen-core formation and long-range frustrations. While frozen cores are identified by a local whitening algorithm, long-range frustrations are very difficult to trace, and they make an entropic belief-propagation (BP) algorithm fail to converge. For BP to reach a fixed point the spin values of a tiny fraction of variables (chosen according to the whitening algorithm) are externally fixed during the iteration. From the calculated entropy values, we infer that, for a large random 3-SAT formula with constraint density close to the satisfiability threshold, the solutions obtained by the survey-propagation or the walksat algorithm belong neither to the most dominating clusters of the formula nor to the most abundant clusters. This work indicates that a single solution cluster of a random 3-SAT formula may have further community structures.

13 pages, 6 figures. Final version as published in PRE

References in corpus (28)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• The Entropy of the K-Satisfiability Problem
• Loop series for discrete statistical models on graphs
• Survey Propagation as local equilibrium equations
• A variational description of the ground state structure in random satisfiability problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• A ferromagnet with a glass transition
• On the freezing of variables in random constraint satisfaction problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• On the dynamics of the glass transition on Bethe lattices
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Focused Local Search for Random 3-Satisfiability
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• Landscape of solutions in constraint satisfaction problems
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Locked constraint satisfaction problems
• On local equilibrium equations for clustering states
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems

Cited by in corpus (14)

• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Inducing Effect on the Percolation Transition in Complex Networks
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Solving the undirected feedback vertex set problem by local search
• Energy landscapes of combinatorial optimization in Ising machines
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Maximally flexible solutions of a random $K$-satisfiability formula
• Counting solutions from finite samplings
• Circumventing spin glass traps by microcanonical spontaneous symmetry breaking
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• CCCP Algorithms to Minimize the Bethe free energy of 3-SAT Problem