ITP OpenIR  > SCI期刊论文
Zhou, Haijun
Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula
Source PublicationEUROPEAN PHYSICAL JOURNAL B
KeywordRandom Satisfiability Problems K-sat Algorithm Phase
AbstractRandom 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 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 a parts per thousand alpha(j). The glassy dynamical behavior of SEQSAT for alpha a parts per thousand yen 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 a parts per thousand yen 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.
2010
ISSN1434-6028
Volume73Issue:4Pages:617-624
Subject AreaPhysics
Indexed BySCI
Funding OrganizationNational Science Foundation of China[10774150]; China 973-Program[2007CB935903] ; National Science Foundation of China[10774150]; China 973-Program[2007CB935903] ; National Science Foundation of China[10774150]; China 973-Program[2007CB935903] ; National Science Foundation of China[10774150]; China 973-Program[2007CB935903]
Citation statistics
Cited Times:8[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/5166
CollectionSCI期刊论文
Recommended Citation
GB/T 7714
Zhou, Haijun. Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula[J]. EUROPEAN PHYSICAL JOURNAL B,2010,73(4):617-624.
APA Zhou, Haijun.(2010).Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula.EUROPEAN PHYSICAL JOURNAL B,73(4),617-624.
MLA Zhou, Haijun."Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula".EUROPEAN PHYSICAL JOURNAL B 73.4(2010):617-624.
Files in This Item:
File Name/Size DocType Version Access License
Glassy behavior and (1414KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhou, Haijun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou, Haijun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou, Haijun]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.