Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula
文献类型：期刊论文
| 作者 | Zhou, Haijun
|
| 刊名 | EUROPEAN PHYSICAL JOURNAL B
 |
| 出版日期 | 2010 |
| 卷号 | 73期号:4页码:617-624 |
| 关键词 | Random Satisfiability Problems K-sat Algorithm Phase |
| ISSN号 | 1434-6028 |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| URL标识 | 查看原文 |
| WOS记录号 | WOS:000275417600018 |
| 公开日期 | 2012-08-02 |
| 源URL | [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. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。