Communities of solutions in single solution clusters of a random K-satisfiability formula
文献类型：期刊论文
| 作者 | Zhou, Haijun ; Ma, Hui; Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
|
| 刊名 | PHYSICAL REVIEW E
 |
| 出版日期 | 2009 |
| 卷号 | 80期号:6页码:- |
| 关键词 | Constraint Satisfaction Problems Phase |
| ISSN号 | 1539-3755 |
| 英文摘要 | The solution space of a K-satisfiability (K-SAT) formula is a collection of solution clusters, each of which contains all the solutions that are mutually reachable through a sequence of single-spin flips. Knowledge of the statistical property of solution clusters is valuable for a complete understanding of the solution space structure and the computational complexity of the random K-SAT problem. This paper explores single solution clusters of random 3- and 4-SAT formulas through unbiased and biased random-walk processes and the replica-symmetric cavity method of statistical physics. We find that the giant connected component of the solution space has already formed many different communities when the constraint density of the formula is still lower than the solution space clustering transition point. Solutions of the same community are more similar with each other and more densely connected with each other than with the other solutions. The entropy density of a solution community is calculated using belief propagation and is found to be different for different communities of the same cluster. When the constraint density is beyond the clustering transition point, the same behavior is observed for the solution clusters reached by several stochastic search algorithms. Taking together, the results of this work suggest a refined picture on the evolution of the solution space structure of the random K-SAT problem; they may also be helpful for designing heuristic algorithms. |
| 学科主题 | Physics |
| URL标识 | 查看原文 |
| WOS记录号 | WOS:000273228000020 |
| 公开日期 | 2012-08-02 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/5204]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 通讯作者 | Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhou, Haijun,Ma, Hui,Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China. Communities of solutions in single solution clusters of a random K-satisfiability formula[J]. PHYSICAL REVIEW E,2009,80(6):-. |
| APA | Zhou, Haijun,Ma, Hui,&Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China.(2009).Communities of solutions in single solution clusters of a random K-satisfiability formula.PHYSICAL REVIEW E,80(6),-. |
| MLA | Zhou, Haijun,et al."Communities of solutions in single solution clusters of a random K-satisfiability formula".PHYSICAL REVIEW E 80.6(2009):-. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。