From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
文献类型：期刊论文
| 作者 | Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China; Li, Kang; Ma, Hui; Zhou, Haijun
|
| 刊名 | PHYSICAL REVIEW E
 |
| 出版日期 | 2009 |
| 卷号 | 79期号:3页码:- |
| 关键词 | Constraint Satisfaction Problems Random Satisfiability Problems Message-passing Algorithms Computational-complexity Glass-transition |
| ISSN号 | 1539-3755 |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| URL标识 | 查看原文 |
| WOS记录号 | WOS:000264767300021 |
| 公开日期 | 2012-08-02 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/5367]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 通讯作者 | Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China,Li, Kang,Ma, Hui,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, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China,Li, Kang,Ma, Hui,&Zhou, Haijun.(2009).From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy.PHYSICAL REVIEW E,79(3),-. |
| MLA | Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China,et al."From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy".PHYSICAL REVIEW E 79.3(2009):-. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。