ITP OpenIR  > 理论物理所科研产出  > SCI论文
Li, Kang; Ma, Hui; Zhou, Haijun; Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
Source PublicationPHYSICAL REVIEW E
KeywordConstraint Satisfaction Problems Random Satisfiability Problems Message-passing Algorithms Computational-complexity Glass-transition
AbstractA solution to a 3-satisfiability (3-SAT) formula can be expanded into a cluster, all other solutions of which are reachable from this one through a sequence of single-spin flips. Some variables in the solution cluster are frozen to the same spin values by one of two different mechanisms: frozen-core formation and long-range frustrations. While frozen cores are identified by a local whitening algorithm, long-range frustrations are very difficult to trace, and they make an entropic belief-propagation (BP) algorithm fail to converge. For the BP algorithm to reach a fixed point, the spin values of a tiny fraction of variables (chosen according to the whitening algorithm) are externally fixed during the iteration. From the calculated entropy values, we infer that, for a large random 3-SAT formula with constraint density close to the satisfiability threshold, the solutions obtained by the survey-propagation or WALKSAT algorithms belong neither to the most dominating clusters of the formula nor to the most abundant clusters. This work indicates that a single-solution cluster of a random 3-SAT formula may have further community structures.
2009
ISSN1539-3755
Volume79Issue:3Pages:-
Subject AreaPhysics
Indexed BySCI
Funding OrganizationNSFC[10774150] ; NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150]
Citation statistics
Cited Times:13[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/5367
Collection理论物理所科研产出_SCI论文
Corresponding AuthorLi, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
Recommended Citation
GB/T 7714
Li, Kang,Ma, Hui,Zhou, Haijun,et al. From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy[J]. PHYSICAL REVIEW E,2009,79(3):-.
APA Li, Kang,Ma, Hui,Zhou, Haijun,&Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China.(2009).From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy.PHYSICAL REVIEW E,79(3),-.
MLA Li, Kang,et al."From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy".PHYSICAL REVIEW E 79.3(2009):-.
Files in This Item:
File Name/Size DocType Version Access License
From one solution of(199KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Li, Kang]'s Articles
[Ma, Hui]'s Articles
[Zhou, Haijun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Li, Kang]'s Articles
[Ma, Hui]'s Articles
[Zhou, Haijun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Li, Kang]'s Articles
[Ma, Hui]'s Articles
[Zhou, Haijun]'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.