Super solutions of random (3+p)-SAT

doi:10.1016/j.tcs.2019.04.015

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 应用数学研究所

	Super solutions of random (3+p)-SAT
	Wang, Bin2 ; Zhou, Guangyan 1
刊名	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
语种	英语
出版者	ELSEVIER
WOS记录号	WOS:000491216500002
内容类型	期刊论文
源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.