Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula

DOI10.1140/EPJB/E2010-00021-XMaRDI QIDQ977543zbMATH OpenOpenAlexFDO

Authors Haijun Zhou

Publication date 22 June 2010

Published in The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.0295

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Combinatorial optimization (90C27)

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 { t SEQSAT}, which satisfies a $K$-SAT formula in a sequential manner. Before satisfying each newly added clause, { t 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 $alph{a}_{cm}$; however it slows down considerably as $alpha>alph{a}_{cm}$ and finally reaches a jammed state at $alphaapproxalph{a}_j$. The glassy dynamical behavior of { t SEQSAT} for $alphageqalph{a}_{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 $alph{a}_j$ is larger than the solution space clustering transition point $alph{a}_d$, and its value can be predicted by a long-range frustration mean-field theory. For random $K$-SAT with $Kgeq4$, however, our simulation results indicate that $alph{a}_j=alph{a}_d$. The relevance of this work for understanding the dynamic properties of glassy systems is also discussed.

Recommendations

• Jamming percolation and glassy dynamics
• A combinatorial approach to a model of constrained random walkers
• On the solution of a ``solvable model of an ideal Glass of hard spheres displaying a jamming transition
• Jamming of multiple persistent random walkers in arbitrary spatial dimension
• On the existence of a glass transition in a random energy model
• Cooperative behavior of kinetically constrained lattice gas models of glassy dynamics
• Exact solution of a jamming transition: Closed equations for a bootstrap percolation problem
• From random walks to spin glasses

Cites work

• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• Phase Transitions in Combinatorial Optimization Problems

Cited in

(1)

• Criticality and heterogeneity in the solution space of random constraint satisfaction problems

This page was built for publication: Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q977543)