ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zeng, Y; Zhou, HJ; Zeng, Y (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.
Solution Space Coupling in the Random K-Satisfiability Problem
发表期刊COMMUNICATIONS IN THEORETICAL PHYSICS
语种英语
关键词Constraint Satisfaction Problems Glass-transition Entropy
摘要The random K-satisfiability (K-SAT) problem is very difficult when the clause density is close to the satisfiability threshold. In this paper we study this problem from the perspective of solution space coupling. We divide a given difficult random K-SAT formula into two easy sub-formulas and let the two corresponding solution spaces to interact with each other through a coupling field x. We investigate the statistical mechanical property of this coupled system by mean field theory and computer simulations. The coupled system has an ergodicity-breaking (clustering) transition at certain critical value x(d) of the coupling field. At this transition point, the mean overlap value between the solutions of the two solution spaces is very close to I. The mean energy density of the coupled system at its clustering transition point is less than the mean energy density of the original K-SAT problem at the temperature-induced clustering transition point. The implications of this work for designing new heuristic K-SAT solvers are discussed.
2013
ISSN0253-6102
卷号60期号:3页码:363-374
学科领域Physics
收录类别SCI
项目资助者Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02]; Natural National Science Foundation of China [11121403, 11225526] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02]; Natural National Science Foundation of China [11121403, 11225526] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02]; Natural National Science Foundation of China [11121403, 11225526] ; Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02]; Natural National Science Foundation of China [11121403, 11225526]
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/15278
专题理论物理所科研产出_SCI论文
通讯作者Zeng, Y (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.
推荐引用方式
GB/T 7714
Zeng, Y,Zhou, HJ,Zeng, Y . Solution Space Coupling in the Random K-Satisfiability Problem[J]. COMMUNICATIONS IN THEORETICAL PHYSICS,2013,60(3):363-374.
APA Zeng, Y,Zhou, HJ,&Zeng, Y .(2013).Solution Space Coupling in the Random K-Satisfiability Problem.COMMUNICATIONS IN THEORETICAL PHYSICS,60(3),363-374.
MLA Zeng, Y,et al."Solution Space Coupling in the Random K-Satisfiability Problem".COMMUNICATIONS IN THEORETICAL PHYSICS 60.3(2013):363-374.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Solution Space Coupl(1108KB) 开放获取使用许可请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Zeng, Y]的文章
[Zhou, HJ]的文章
[Zeng, Y (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]的文章
百度学术
百度学术中相似的文章
[Zeng, Y]的文章
[Zhou, HJ]的文章
[Zeng, Y (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]的文章
必应学术
必应学术中相似的文章
[Zeng, Y]的文章
[Zhou, HJ]的文章
[Zeng, Y (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Zhong Guan Cun East Rd 55, Beijing 100190, Peoples R China.]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

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