Eur. Phys. J. B 73, 617-624 (2010)
https://doi.org/10.1140/epjb/e2010-00021-x

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

¹ Key Laboratory of Frontiers in Theoretical Physics and Kavli Institute for Theoretical Physics, 100190, Beijing, P.R. China
² Institute of Theoretical Physics, Chinese Academy of Sciences, 100190, Beijing, P.R. China

Corresponding author: zhouhj@itp.ac.cn

Received: 2 July 2009
Revised: 1 December 2009
Published online: 21 January 2010

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 SEQSAT, which satisfies a K-SAT formula in a sequential manner. Before satisfying each newly added clause, SEQSAT walk randomly by single-spin flips in a solution cluster of the old subformula. This search process is efficient when the constraint density α of the satisfied subformula is less than certain value α_cm; however it slows down considerably as α > α_cm and finally reaches a jammed state at α ≈ α_j. The glassy dynamical behavior of SEQSAT for α ≥ α_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 α_j is larger than the solution space clustering transition point α_d, and its value can be predicted by a long-range frustration mean-field theory. For random K-SAT with K ≥ 4, however, our simulation results indicate that α_j = α_d. The relevance of this work for understanding the dynamic properties of glassy systems is also discussed.