ITP OpenIR  > 理论物理所1978-2010年知识产出
From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
Li, Kang; Ma, Hui; Zhou, Haijun; Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
2009
发表期刊PHYSICAL REVIEW E
ISSN1539-3755
卷号79期号:3页码:-
摘要A solution to a 3-satisfiability (3-SAT) formula can be expanded into a cluster, all other solutions of which are reachable from this one through a sequence of single-spin flips. Some variables in the solution cluster are frozen to the same spin values by one of two different mechanisms: frozen-core formation and long-range frustrations. While frozen cores are identified by a local whitening algorithm, long-range frustrations are very difficult to trace, and they make an entropic belief-propagation (BP) algorithm fail to converge. For the BP algorithm to reach a fixed point, the spin values of a tiny fraction of variables (chosen according to the whitening algorithm) are externally fixed during the iteration. From the calculated entropy values, we infer that, for a large random 3-SAT formula with constraint density close to the satisfiability threshold, the solutions obtained by the survey-propagation or WALKSAT algorithms belong neither to the most dominating clusters of the formula nor to the most abundant clusters. This work indicates that a single-solution cluster of a random 3-SAT formula may have further community structures.
部门归属[Li, K; Ma, H; Zhou, HJ] Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
关键词Constraint Satisfaction Problems Random Satisfiability Problems Message-passing Algorithms Computational-complexity Glass-transition
学科领域Physics
资助者NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150]
URL查看原文
收录类别SCI
资助者NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150]
WOS记录号WOS:000264767300021
引用统计
被引频次:13[WOS]   [WOS记录]     [WOS相关记录]
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/5367
专题理论物理所1978-2010年知识产出
通讯作者Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714
Li, Kang,Ma, Hui,Zhou, Haijun,et al. From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy[J]. PHYSICAL REVIEW E,2009,79(3):-.
APA Li, Kang,Ma, Hui,Zhou, Haijun,&Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China.(2009).From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy.PHYSICAL REVIEW E,79(3),-.
MLA Li, Kang,et al."From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy".PHYSICAL REVIEW E 79.3(2009):-.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
From one solution of(199KB) 开放获取使用许可请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Li, Kang]的文章
[Ma, Hui]的文章
[Zhou, Haijun]的文章
百度学术
百度学术中相似的文章
[Li, Kang]的文章
[Ma, Hui]的文章
[Zhou, Haijun]的文章
必应学术
必应学术中相似的文章
[Li, Kang]的文章
[Ma, Hui]的文章
[Zhou, Haijun]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

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