ITP OpenIR  > 理论物理所1978-2010年知识产出
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
2009
发表期刊PHYSICAL REVIEW E
ISSN1539-3755
卷号80期号:6页码:-
摘要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.
部门归属[Zhou, HJ; Ma, H] Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China; [Zhou, HJ] Chinese Acad Sci, Inst Theoret Phys, Kavli Inst Theoret Phys, Beijing 100190, Peoples R China
关键词Constraint Satisfaction Problems Phase
学科领域Physics
资助者NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903]
URL查看原文
收录类别SCI
资助者NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903]
WOS记录号WOS:000273228000020
引用统计
被引频次:12[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符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):-.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Communities of solut(930KB) 开放获取使用许可请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zhou, Haijun]的文章
[Ma, Hui]的文章
[Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China]的文章
百度学术
百度学术中相似的文章
[Zhou, Haijun]的文章
[Ma, Hui]的文章
[Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China]的文章
必应学术
必应学术中相似的文章
[Zhou, Haijun]的文章
[Ma, Hui]的文章
[Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

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