Knowledge Management System of Institute of Theoretical Physics, CAS
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 | |
Source Publication | COMMUNICATIONS IN THEORETICAL PHYSICS |
Language | 英语 |
Keyword | Constraint Satisfaction Problems Glass-transition Entropy |
Abstract | 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 | |
ISSN | 0253-6102 |
Volume | 60Issue:3Pages:363-374 |
Subject Area | Physics |
Indexed By | SCI |
Funding Organization | 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] |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.itp.ac.cn/handle/311006/15278 |
Collection | 理论物理所科研产出_SCI论文 |
Corresponding Author | 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. |
Recommended Citation 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. |
Files in This Item: | ||||||
File Name/Size | DocType | Version | Access | License | ||
Solution Space Coupl（1108KB） | 开放获取 | License | Application Full Text |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment