ITP OpenIR  > 理论物理所2013年知识产出
Solution Space Coupling in the Random K-Satisfiability Problem
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.
2013
发表期刊COMMUNICATIONS IN THEORETICAL PHYSICS
ISSN0253-6102
卷号60期号:3页码:363-374
摘要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.
部门归属[Zeng Ying; Zhou Hai-Jun] Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China
关键词Constraint Satisfaction Problems Glass-transition Entropy
学科领域Physics
资助者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]
收录类别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]
WOS记录号WOS:000325042500018
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/15278
专题理论物理所2013年知识产出
通讯作者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)
暂无评论
 

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