2009/07/31 by Haijun Zhou · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Optimization Algorithms Research #Cluster (spacecraft) #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Jamming #Metaheuristic Optimization Algorithms Research #Point process #Process (computing) #Random walk #Simple (philosophy) #Space (punctuation) #cond-mat.dis-nn
paper · pdf · doi:10.1140/epjb/e2010-00021-x
10 pages, 6 figures, 1 table, a mistake of numerical simulation corrected, and new results added
arxiv created 2009/12/20 · openalex publication_date 2010/01/21 · arxiv updated 2015/05/13 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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 α 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 \tt 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.