Solution Space Coupling in the Random K-Satisfiability Problem
文献类型：期刊论文
| 作者 | Zhou, HJ
|
| 刊名 | COMMUNICATIONS IN THEORETICAL PHYSICS
 |
| 出版日期 | 2013 |
| 卷号 | 60期号:3页码:363-374 |
| 关键词 | CONSTRAINT SATISFACTION PROBLEMS GLASS-TRANSITION ENTROPY |
| ISSN号 | 0253-6102 |
| 通讯作者 | 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. |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| 收录类别 | SCI |
| 资助信息 | Knowledge Innovation Program of Chinese Academy of Sciences [KJCX2-EW-J02]; Natural National Science Foundation of China [11121403, 11225526] |
| 语种 | 英语 |
| WOS记录号 | WOS:000325042500018 |
| 公开日期 | 2014-04-25 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/15278]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 推荐引用方式 GB/T 7714 | Zhou, HJ. Solution Space Coupling in the Random K-Satisfiability Problem[J]. COMMUNICATIONS IN THEORETICAL PHYSICS,2013,60(3):363-374. |
| APA | Zhou, HJ.(2013).Solution Space Coupling in the Random K-Satisfiability Problem.COMMUNICATIONS IN THEORETICAL PHYSICS,60(3),363-374. |
| MLA | Zhou, HJ."Solution Space Coupling in the Random K-Satisfiability Problem".COMMUNICATIONS IN THEORETICAL PHYSICS 60.3(2013):363-374. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。