Witness of unsatisfiability for a random 3-satisfiability formula
文献类型：期刊论文
| 作者 | Zhou, HJ
|
| 刊名 | PHYSICAL REVIEW E
 |
| 出版日期 | 2013 |
| 卷号 | 87期号:5页码:52807 |
| 关键词 | CONSTRAINT SATISFACTION PROBLEMS RANDOM K-SAT SATISFIABILITY PROBLEMS CAVITY METHOD |
| ISSN号 | 1539-3755 |
| 通讯作者 | Wu, LL (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China. |
| 英文摘要 | 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. |
| 学科主题 | Physics |
| 收录类别 | 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 |
| 原文出处 | http://dx.doi.org/10.1103/PhysRevE.87.052807 |
| 语种 | 英语 |
| WOS记录号 | WOS:000319254900009 |
| 公开日期 | 2014-04-25 |
| 源URL | [http://ir.itp.ac.cn/handle/311006/15361]  |
| 专题 | 理论物理研究所_理论物理所1978-2010年知识产出 |
| 推荐引用方式 GB/T 7714 | Zhou, HJ. Witness of unsatisfiability for a random 3-satisfiability formula[J]. PHYSICAL REVIEW E,2013,87(5):52807. |
| APA | Zhou, HJ.(2013).Witness of unsatisfiability for a random 3-satisfiability formula.PHYSICAL REVIEW E,87(5),52807. |
| MLA | Zhou, HJ."Witness of unsatisfiability for a random 3-satisfiability formula".PHYSICAL REVIEW E 87.5(2013):52807. |
入库方式： OAI收割
来源：理论物理研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。