中国科学院理论物理研究所机构知识库
Advanced  
ITP OpenIR  > 理论物理所1978-2010年知识产出  > 期刊论文
题名: From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
作者: 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
学科分类: Physics
通讯作者: Li, K , Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
部门归属: [Li, K; Ma, H; Zhou, HJ] Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
英文摘要: 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.
资助者: NSFC[10774150]
收录类别: SCI
原文出处: 查看原文
WOS记录号: WOS:000264767300021
Citation statistics: 
内容类型: 期刊论文
URI标识: http://ir.itp.ac.cn/handle/311006/5367
Appears in Collections:理论物理所1978-2010年知识产出_期刊论文

Files in This Item: Download All
File Name/ File Size Content Type Version Access License
From one solution of a 3-satisfiability formula to a solution cluster Frozen variables and entropy.pdf(199KB)----开放获取View Download

Recommended Citation:
Li, Kang,Ma, Hui,Zhou, Haijun. From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy[J]. PHYSICAL REVIEW E,2009,79(3):-.
Service
 Recommend this item
 Sava as my favorate item
 Show this item's statistics
 Export Endnote File
Google Scholar
 Similar articles in Google Scholar
 [Li, Kang]'s Articles
 [Ma, Hui]'s Articles
 [Zhou, Haijun]'s Articles
CSDL cross search
 Similar articles in CSDL Cross Search
 [Li, Kang]‘s Articles
 [Ma, Hui]‘s Articles
 [Zhou, Haijun]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
  Add to CiteULike  Add to Connotea  Add to Del.icio.us  Add to Digg  Add to Reddit 
文件名: From one solution of a 3-satisfiability formula to a solution cluster Frozen variables and entropy.pdf
格式: Adobe PDF
此文件暂不支持浏览
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院理论物理研究所 - Feedback
Powered by CSpace