QQ客服 官方微博 反馈留言

	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):-.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

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