CSpace  > 应用数学研究所
Super solutions of random (3+p)-SAT
Wang, Bin1; Zhou, Guangyan2
AbstractIn 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.
Keyword(1,0)-satisfiable Super solution Phase transition Unit Clause
Funding ProjectNational Natural Science Fund of China[61702019] ; National Natural Science Fund of China[11501017]
WOS Research AreaComputer Science
WOS SubjectComputer Science, Theory & Methods
WOS IDWOS:000491216500002
Citation statistics
Document Type期刊论文
Corresponding AuthorZhou, Guangyan
Affiliation1.Chinese Acad Sci, Acad Math & Syst Sci, Key Lab Random Complex Struct & Data Sci, Beijing 100190, Peoples R China
2.Beijing Technol & Business Univ, Dept Math, Beijing 100048, Peoples R China
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wang, Bin]'s Articles
[Zhou, Guangyan]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wang, Bin]'s Articles
[Zhou, Guangyan]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wang, Bin]'s Articles
[Zhou, Guangyan]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.