中国科学院理论物理研究所机构知识库
Advanced  
ITP OpenIR  > 理论物理所2013年知识产出  > 期刊论文
题名: Witness of unsatisfiability for a random 3-satisfiability formula
作者: Wu, LL ;  Zhou, HJ ;  Alava, M ;  Aurell, E ;  Orponen, P
刊名: PHYSICAL REVIEW E
出版日期: 2013
卷号: 87, 期号:5, 页码:52807
关键词: CONSTRAINT SATISFACTION PROBLEMS ;  RANDOM K-SAT ;  SATISFIABILITY PROBLEMS ;  CAVITY METHOD
学科分类: Physics
通讯作者: Wu, LL (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
部门归属: [Wu, Lu-Lu; Zhou, Hai-Jun] Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China; [Alava, Mikko] Aalto Univ, Dept Appl Phys, FI-00076 Aalto, Finland; [Aurell, Erik] KTH, ACCESS Linnaeus Ctr, Stockholm, Sweden; [Aurell, Erik] AlbaNova Univ Ctr, Dept Computat Biol, S-10691 Stockholm, Sweden; [Aurell, Erik] Aalto Univ, Sch Sci, FI-00076 Aalto, Finland; [Orponen, Pekka] Aalto Univ, Dept Informat & Comp Sci, FI-00076 Aalto, Finland
英文摘要: The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density alpha exceeds a critical value alpha(s) approximate to 4.267. Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density alpha > 19. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when a scales at least linearly with the variable number N, but the focused local search algorithm works for clause density alpha > cN(b) with b approximate to 0.59 and prefactor c approximate to 8. The exponent b can be further decreased by enlarging the single parameter S of the focused local search algorithm.
资助者: Knowledge Innovation Program of the Chinese Academy of Sciences [KJCX2-EW-J02]; National Science Foundation of China [11121403, 11225526]; Academy of Finland as part of its Finland Distinguished Professor Program [129024/Aurell]; Academy of Finland as part of its Finland Distinguished Professor Program through the Centres of Excellence COIN; COMP
收录类别: SCI
原文出处: 查看原文
语种: 英语
WOS记录号: WOS:000319254900009
Citation statistics: 
内容类型: 期刊论文
URI标识: http://ir.itp.ac.cn/handle/311006/15361
Appears in Collections:理论物理所2013年知识产出 _期刊论文

Files in This Item: Download All
File Name/ File Size Content Type Version Access License
Witness of unsatisfiability for a random 3-satisfiability formula.pdf(427KB)----开放获取View Download

Recommended Citation:
Wu, LL,Zhou, HJ,Alava, M,et al. Witness of unsatisfiability for a random 3-satisfiability formula[J]. PHYSICAL REVIEW E,2013,87(5):52807.
Service
 Recommend this item
 Sava as my favorate item
 Show this item's statistics
 Export Endnote File
Google Scholar
 Similar articles in Google Scholar
 [Wu, LL]'s Articles
 [Zhou, HJ]'s Articles
 [Alava, M]'s Articles
CSDL cross search
 Similar articles in CSDL Cross Search
 [Wu, LL]‘s Articles
 [Zhou, HJ]‘s Articles
 [Alava, M]‘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 
文件名: Witness of unsatisfiability for a random 3-satisfiability 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