Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula

Abstract

Random $K$-satisfiability ($K$-SAT) is a model system for studying typical-case complexity of combinatorial optimization. Recent theoretical and simulation work revealed that the solution space of a random $K$-SAT formula has very rich structures, including the emergence of solution communities within single solution clusters. In this paper we investigate the influence of the solution space landscape to a simple stochastic local search process {\tt SEQSAT}, which satisfies a $K$-SAT formula in a sequential manner. Before satisfying each newly added clause, {\tt SEQSAT} walk randomly by single-spin flips in a solution cluster of the old subformula. This search process is efficient when the constraint density $\alpha$ of the satisfied subformula is less than certain value ${\alpha }_{cm}$; however it slows down considerably as $\alpha >{\alpha }_{cm}$ and finally reaches a jammed state at $\alpha \approx {\alpha }_j$. The glassy dynamical behavior of {\tt SEQSAT} for $\alpha \ge {\alpha }_{cm}$ probably is due to the entropic trapping of various communities in the solution cluster of the satisfied subformula. For random 3-SAT, the jamming transition point ${\alpha }_j$ is larger than the solution space clustering transition point ${\alpha }_d$, and its value can be predicted by a long-range frustration mean-field theory. For random $K$-SAT with $K\ge 4$, however, our simulation results indicate that ${\alpha }_j={\alpha }_d$. The relevance of this work for understanding the dynamic properties of glassy systems is also discussed.

10 pages, 6 figures, 1 table, a mistake of numerical simulation corrected, and new results added

References in corpus (10)

• Glassy dynamics of kinetically constrained models
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• A Landscape Analysis of Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Quantum phase transitions in a two-dimensional quantum XYX model: Ground-state fidelity and entanglement

Cited by in corpus (7)

• Entropy landscape of solutions in the binary perceptron problem
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Learning by random walks in the weight space of the Ising perceptron
• Combined local search strategy for learning in networks of binary synapses
• Counting solutions from finite samplings
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Criticality and Heterogeneity in the Solution Space of Random Constraint Satisfaction Problems