中国科学院理论物理研究所机构知识库
Advanced  
ITP OpenIR  > 理论物理所1978-2010年知识产出  > 期刊论文
题名: Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula
作者: Zhou, Haijun
刊名: EUROPEAN PHYSICAL JOURNAL B
出版日期: 2010
卷号: 73, 期号:4, 页码:617-624
关键词: RANDOM SATISFIABILITY PROBLEMS ;  K-SAT ;  ALGORITHM ;  PHASE
学科分类: Physics
部门归属: [Zhou, HJ] Chinese Acad Sci, Inst Theoret Phys, Beijing 100190, Peoples R China
英文摘要: Random K-satisfiability (K-SAT) is a model system for studying typical-case complexity of combinatorial optimization. Recent theoretical and simulation work revealed that the solution space of a random K-SAT formula has very rich structures, including the emergence of solution communities within single solution clusters. In this paper we investigate the influence of the solution space landscape to a simple stochastic local search process SEQSAT, which satisfies a K-SAT formula in a sequential manner. Before satisfying each newly added clause, SEQSAT walk randomly by single-spin flips in a solution cluster of the old subformula. This search process is efficient when the constraint density alpha of the satisfied subformula is less than certain value alpha(cm); however it slows down considerably as alpha > alpha(cm) and finally reaches a jammed state at alpha a parts per thousand alpha(j). The glassy dynamical behavior of SEQSAT for alpha a parts per thousand yen alpha(cm) probably is due to the entropic trapping of various communities in the solution cluster of the satisfied subformula. For random 3-SAT, the jamming transition point alpha(j) is larger than the solution space clustering transition point alpha(d), and its value can be predicted by a long-range frustration mean-field theory. For random K-SAT with K a parts per thousand yen 4, however, our simulation results indicate that alpha(j) = alpha(d). The relevance of this work for understanding the dynamic properties of glassy systems is also discussed.
资助者: National Science Foundation of China[10774150]; China 973-Program[2007CB935903]
收录类别: SCI
原文出处: 查看原文
WOS记录号: WOS:000275417600018
Citation statistics: 
内容类型: 期刊论文
URI标识: http://ir.itp.ac.cn/handle/311006/5166
Appears in Collections:理论物理所1978-2010年知识产出_期刊论文

Files in This Item: Download All
File Name/ File Size Content Type Version Access License
Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula.pdf(1414KB)----开放获取View Download

Recommended Citation:
Zhou, Haijun. Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula[J]. EUROPEAN PHYSICAL JOURNAL B,2010,73(4):617-624.
Service
 Recommend this item
 Sava as my favorate item
 Show this item's statistics
 Export Endnote File
Google Scholar
 Similar articles in Google Scholar
 [Zhou, Haijun]'s Articles
CSDL cross search
 Similar articles in CSDL Cross Search
 [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 
文件名: Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula.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