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
Source PublicationCOMMUNICATIONS IN THEORETICAL PHYSICS
Language英语
KeywordConstraint Satisfaction Problems Glass-transition Entropy
AbstractThe 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
Volume60Issue:3Pages:363-374
Subject AreaPhysics
Indexed BySCI
Funding OrganizationKnowledge 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期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/15278
CollectionSCI期刊论文
Corresponding AuthorZeng, 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) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zeng, Y]'s Articles
[Zhou, HJ]'s Articles
[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.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zeng, Y]'s Articles
[Zhou, HJ]'s Articles
[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.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zeng, Y]'s Articles
[Zhou, HJ]'s Articles
[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.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.