ITP OpenIR  > 理论物理所科研产出  > SCI论文
Zhou, Haijun; Ma, Hui; Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
Communities of solutions in single solution clusters of a random K-satisfiability formula
Source PublicationPHYSICAL REVIEW E
KeywordConstraint Satisfaction Problems Phase
AbstractThe solution space of a K-satisfiability (K-SAT) formula is a collection of solution clusters, each of which contains all the solutions that are mutually reachable through a sequence of single-spin flips. Knowledge of the statistical property of solution clusters is valuable for a complete understanding of the solution space structure and the computational complexity of the random K-SAT problem. This paper explores single solution clusters of random 3- and 4-SAT formulas through unbiased and biased random-walk processes and the replica-symmetric cavity method of statistical physics. We find that the giant connected component of the solution space has already formed many different communities when the constraint density of the formula is still lower than the solution space clustering transition point. Solutions of the same community are more similar with each other and more densely connected with each other than with the other solutions. The entropy density of a solution community is calculated using belief propagation and is found to be different for different communities of the same cluster. When the constraint density is beyond the clustering transition point, the same behavior is observed for the solution clusters reached by several stochastic search algorithms. Taking together, the results of this work suggest a refined picture on the evolution of the solution space structure of the random K-SAT problem; they may also be helpful for designing heuristic algorithms.
2009
ISSN1539-3755
Volume80Issue:6Pages:-
Subject AreaPhysics
Indexed BySCI
Funding OrganizationNSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903] ; NSFC[10774150]; China 973-Program[2007CB935903]
Citation statistics
Cited Times:13[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/5204
Collection理论物理所科研产出_SCI论文
Corresponding AuthorZhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China
Recommended Citation
GB/T 7714
Zhou, Haijun,Ma, Hui,Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China. Communities of solutions in single solution clusters of a random K-satisfiability formula[J]. PHYSICAL REVIEW E,2009,80(6):-.
APA Zhou, Haijun,Ma, Hui,&Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China.(2009).Communities of solutions in single solution clusters of a random K-satisfiability formula.PHYSICAL REVIEW E,80(6),-.
MLA Zhou, Haijun,et al."Communities of solutions in single solution clusters of a random K-satisfiability formula".PHYSICAL REVIEW E 80.6(2009):-.
Files in This Item:
File Name/Size DocType Version Access License
Communities of solut(930KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Zhou, Haijun]'s Articles
[Ma, Hui]'s Articles
[Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China]'s Articles
Baidu academic
Similar articles in Baidu academic
[Zhou, Haijun]'s Articles
[Ma, Hui]'s Articles
[Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, Beijing 100190, Peoples R China]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Zhou, Haijun]'s Articles
[Ma, Hui]'s Articles
[Zhou, HJ , Chinese Acad Sci, Key Lab Frontiers Theoret Phys, 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.