Super solutions of random (3+p)-SAT
文献类型：期刊论文
| 作者 | Wang, Bin2 ; Zhou, Guangyan1
|
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2019-11-12 |
| 卷号 | 793页码:14-27 |
| 关键词 | (1,0)-satisfiable Super solution Phase transition Unit Clause |
| ISSN号 | 0304-3975 |
| DOI | 10.1016/j.tcs.2019.04.015 |
| 英文摘要 | In this paper, we propose a model named random (3 + p)-SAT, where a random formula phi = phi(n, r, p) contains n variables and rn clauses, and (1 - p)rn of the clauses are 3-clauses and pm of the clauses are 4-clauses. This paper studies the (1, 0)-satisfiability of random (3 + p)-SAT and obtains rigorous results that the exact (1, 0)-satisfiability threshold is r(p)* = 1/3(1 - p) if p <= 3/7. For p >= 3/7, we give lower and upper bounds of the (1, 0)-satisfiability threshold, where the lower bound is obtained by using the Unit-Clause algorithm, and the upper bound is obtained by using a novel way to count precisely the subset of all (1, 0)-satisfying assignments that satisfy a "locally maximum" condition. (C) 2019 Elsevier B.V. All rights reserved. |
| 资助项目 | National Natural Science Fund of China[61702019] ; National Natural Science Fund of China[11501017] |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000491216500002 |
| 出版者 | ELSEVIER |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/35868]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Zhou, Guangyan |
| 作者单位 | 1.Beijing Technol & Business Univ, Dept Math, Beijing 100048, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, Key Lab Random Complex Struct & Data Sci, Beijing 100190, Peoples R China |
| 推荐引用方式 GB/T 7714 | Wang, Bin,Zhou, Guangyan. Super solutions of random (3+p)-SAT[J]. THEORETICAL COMPUTER SCIENCE,2019,793:14-27. |
| APA | Wang, Bin,&Zhou, Guangyan.(2019).Super solutions of random (3+p)-SAT.THEORETICAL COMPUTER SCIENCE,793,14-27. |
| MLA | Wang, Bin,et al."Super solutions of random (3+p)-SAT".THEORETICAL COMPUTER SCIENCE 793(2019):14-27. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。