Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2009-07-02
Physics
Condensed Matter
Disordered Systems and Neural Networks
10 pages, 6 figures, 1 table, a mistake of numerical simulation corrected, and new results added
Scientific paper
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 \geq \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\geq 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.
No associations
LandOfFree
Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-730698