中国科学院理论物理研究所机构知识库
Advanced  
ITP OpenIR  > 理论物理所1978-2010年知识产出  > 期刊论文
题名: Long-range frustration in finite connectivity spin glasses: a mean-field theory and its application to the random K-satisfiability problem
作者: Zhou, HJ
刊名: NEW JOURNAL OF PHYSICS
出版日期: 2005
卷号: 7, 期号:1, 页码:-
关键词: RANDOM 3-SAT ;  NUMBER
学科分类: Physics
通讯作者: Zhou, HJ , Max Planck Inst Colloids & Interfaces, D-14424 Potsdam, Germany.
部门归属: Max Planck Inst Colloids & Interfaces, D-14424 Potsdam, Germany; Chinese Acad Sci, Inst Theoret Phys, Beijing 100080, Peoples R China
英文摘要: A mean-field theory of long-range frustration is constructed for spin glass systems with quenched randomness of vertex-vertex connections and of spin-spin coupling strengths. This theory is applied to a spin glass model of the random K-satisfiability (K-SAT) problem (K = 2 or K = 3). The satisfiability transition in a random 2-SAT formula occurs when the clauses-to-variables ratio alpha approaches alpha(c)(2) = 1. However, long-range frustration among unfrozen variable nodes builds up only when alpha > alpha(R)(2) = 4.4588. For the random 3-SAT problem, we find a long-range frustrated mean-field solution when alpha > alpha(R)(3) = 4.1897. The long-range frustration order parameter R of this solution jumps from zero to a finite positive value at alpha(R)( 3), while the energy density increases only gradually from zero as a function of a. The SAT-UNSAT transition point of this solution is lower than the value of alpha(c)(3) = 4.267 obtained by the survey propagation algorithm. Two possible reasons for this discrepancy are suggested. The zero-temperature phase diagram of the +/- J Viana-Bray model is also determined, which is identical to that of the random 2-SAT problem. The predicted phase transition between a non-frustrated and a long-range frustrated spin glass phase might also be observable in real materials at a finite temperature.
收录类别: SCI
原文出处: 查看原文
WOS记录号: WOS:000229197900001
Citation statistics: 
内容类型: 期刊论文
URI标识: http://ir.itp.ac.cn/handle/311006/13820
Appears in Collections:理论物理所1978-2010年知识产出_期刊论文

Files in This Item: Download All
File Name/ File Size Content Type Version Access License
Long-range frustration in finite connectivity spin glasses a mean-field theory and its application to the random K-satisfiability problem.pdf(273KB)----开放获取View Download

Recommended Citation:
Zhou, HJ. Long-range frustration in finite connectivity spin glasses: a mean-field theory and its application to the random K-satisfiability problem[J]. NEW JOURNAL OF PHYSICS,2005,7(1):-.
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, HJ]'s Articles
CSDL cross search
 Similar articles in CSDL Cross Search
 [Zhou, HJ]‘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 
文件名: Long-range frustration in finite connectivity spin glasses a mean-field theory and its application to the random K-satisfiability problem.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