Knowledge Management System of Institute of Theoretical Physics, CAS
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 Publication | PHYSICAL REVIEW E |
Keyword | Constraint Satisfaction Problems Phase |
Abstract | The 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 | |
ISSN | 1539-3755 |
Volume | 80Issue:6Pages:- |
Subject Area | Physics |
Indexed By | SCI |
Funding Organization | NSFC[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 | |
Document Type | 期刊论文 |
Identifier | http://ir.itp.ac.cn/handle/311006/5204 |
Collection | 理论物理所科研产出_SCI论文 |
Corresponding Author | Zhou, 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） | 开放获取 | License | Application Full Text |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment