Knowledge Management System of Institute of Theoretical Physics, CAS
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 Publication | PHYSICAL REVIEW E |
Keyword | Constraint Satisfaction Problems Random Satisfiability Problems Message-passing Algorithms Computational-complexity Glass-transition |
Abstract | A 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 | |
ISSN | 1539-3755 |
Volume | 79Issue:3Pages:- |
Subject Area | Physics |
Indexed By | SCI |
Funding Organization | NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150] ; NSFC[10774150] |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.itp.ac.cn/handle/311006/5367 |
Collection | SCI期刊论文 |
Corresponding Author | Li, 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） | 开放获取 | License | Application Full Text |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment