ITP OpenIR  > 理论物理所1978-2010年知识产出
Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula
Zhou, Haijun
2010
发表期刊EUROPEAN PHYSICAL JOURNAL B
ISSN1434-6028
卷号73期号:4页码:617-624
摘要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 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.
部门归属[Zhou, HJ] Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
关键词Random Satisfiability Problems K-sat Algorithm Phase
学科领域Physics
资助者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] ; National Science Foundation of China[10774150]; China 973-Program[2007CB935903]
URL查看原文
收录类别SCI
资助者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] ; National Science Foundation of China[10774150]; China 973-Program[2007CB935903]
WOS记录号WOS:000275417600018
引用统计
被引频次:8[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/5166
专题理论物理所1978-2010年知识产出
推荐引用方式
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.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Glassy behavior and (1414KB) 开放获取使用许可请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zhou, Haijun]的文章
百度学术
百度学术中相似的文章
[Zhou, Haijun]的文章
必应学术
必应学术中相似的文章
[Zhou, Haijun]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。