ITP OpenIR  > 理论物理所2013年知识产出
Witness of unsatisfiability for a random 3-satisfiability formula
Wu, LL; Zhou, HJ; Alava, M; Aurell, E; Orponen, P; Wu, LL (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
2013
发表期刊PHYSICAL REVIEW E
ISSN1539-3755
卷号87期号:5页码:52807
摘要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.
部门归属[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
关键词Constraint Satisfaction Problems Random K-sat Satisfiability Problems Cavity Method
学科领域Physics
资助者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 ; 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 ; 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 ; 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
URL查看原文
收录类别SCI
语种英语
资助者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 ; 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 ; 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 ; 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
WOS记录号WOS:000319254900009
引用统计
文献类型期刊论文
条目标识符http://ir.itp.ac.cn/handle/311006/15361
专题理论物理所2013年知识产出
通讯作者Wu, LL (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
推荐引用方式
GB/T 7714
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.
APA Wu, LL,Zhou, HJ,Alava, M,Aurell, E,Orponen, P,&Wu, LL .(2013).Witness of unsatisfiability for a random 3-satisfiability formula.PHYSICAL REVIEW E,87(5),52807.
MLA Wu, LL,et al."Witness of unsatisfiability for a random 3-satisfiability formula".PHYSICAL REVIEW E 87.5(2013):52807.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
Witness of unsatisfi(427KB) 开放获取使用许可请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Wu, LL]的文章
[Zhou, HJ]的文章
[Alava, M]的文章
百度学术
百度学术中相似的文章
[Wu, LL]的文章
[Zhou, HJ]的文章
[Alava, M]的文章
必应学术
必应学术中相似的文章
[Wu, LL]的文章
[Zhou, HJ]的文章
[Alava, M]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。