ITP OpenIR  > SCI期刊论文
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.
Witness of unsatisfiability for a random 3-satisfiability formula
Source PublicationPHYSICAL REVIEW E
Language英语
KeywordConstraint Satisfaction Problems Random K-sat Satisfiability Problems Cavity Method
AbstractThe 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.
2013
ISSN1539-3755
Volume87Issue:5Pages:52807
Subject AreaPhysics
Indexed BySCI
Funding OrganizationKnowledge 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
Citation statistics
Document Type期刊论文
Identifierhttp://ir.itp.ac.cn/handle/311006/15361
CollectionSCI期刊论文
Corresponding AuthorWu, LL (reprint author), Chinese Acad Sci, Inst Theoret Phys, State Key Lab Theoret Phys, Beijing 100190, Peoples R China.
Recommended Citation
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.
Files in This Item:
File Name/Size DocType Version Access License
Witness of unsatisfi(427KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wu, LL]'s Articles
[Zhou, HJ]'s Articles
[Alava, M]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wu, LL]'s Articles
[Zhou, HJ]'s Articles
[Alava, M]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wu, LL]'s Articles
[Zhou, HJ]'s Articles
[Alava, M]'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.