ITP OpenIR  > SCI会议论文
Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
Zhou, HJ
2010
Conference NameInternational Workshop on Statistical-Mechanical Informatics 2010 (IW-SMI 2010)
Source PublicationINTERNATIONAL WORKSHOP ON STATISTICAL-MECHANICAL INFORMATICS 2010 (IW-SMI 2010)
Volume233
Pages12011
Conference DateMAR 07-10, 2010
Conference PlaceKyoto Univ, Kyoto, JAPAN
Author of SourceKyoto Univ
Publication PlaceBRISTOL
ISSN1742-6588
PublisherIOP PUBLISHING LTD
AbstractThe random K-satisfiability (K-SAT) problem is an important problem for studying typical-case complexity of NP-complete combinatorial satisfaction; it is also a representative model of finite-connectivity spin-glasses. In this paper we review our recent efforts on the solution space fine structures of the random K-SAT problem. A heterogeneity transition is predicted to occur in the solution space as the constraint density alpha reaches a critical value alpha(cm). This transition marks the emergency of exponentially many solution communities in the solution space. After the heterogeneity transition the solution space is still ergodic until alpha reaches a larger threshold value alpha(d), at which the solution communities disconnect from each other to become different solution clusters (ergodicity-breaking). The existence of solution communities in the solution space is confirmed by numerical simulations of solution space random walking, and the effect of solution space heterogeneity on a stochastic local search algorithm SEQSAT, which performs a random walk of single-spin flips, is investigated. The relevance of this work to glassy dynamics studies is briefly mentioned.
KeywordCONSTRAINT SATISFACTION PROBLEMS SPIN-GLASSES MEAN-FIELD DYNAMICS LIQUIDS STATES
DOI10.1088/1742-6596/233/1/012011
URL查看原文
Indexed ByCPCI
Language英语
WOS Research AreaComputer Science ; Physics ; Mathematics
WOS SubjectComputer Science, Theory & Methods ; Physics, Applied ; Statistics & Probability
Citation statistics
Cited Times:2[WOS]   [WOS Record]     [Related Records in WOS]
Document Type会议论文
Identifierhttp://ir.itp.ac.cn/handle/311006/23643
CollectionSCI会议论文
AffiliationChinese Acad Sci, Inst Theoret Phys, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
First Author AffilicationInstitute of Theoretical Physics, Chinese Academy of Sciences
Recommended Citation
GB/T 7714
Zhou, HJ. Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations[C]//Kyoto Univ. BRISTOL:IOP PUBLISHING LTD,2010:12011.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhou, HJ]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou, HJ]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou, HJ]'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.