On the Satisfiability Threshold of Regular(k,S)-SAT

摘要：

　　We consider a regular random (k, s)-SAT problem.We show that for all k exceeding an absolute constant k0, with the clause density αureq > 2klog2-klog2/2 + εk, there is no satisfying assignments w.h.p.To the best of our knowledge, it is below the current best known upper bound 2klog2 + εk.The proof directly employs ideas from the 1RSB cavity method and the Survey Propagation calculations.Furthermore, this bound is also blow the asymptotic bound of the uni%rm k-SAT problem, which is known as 2klog 2 (log 2 + 1)/2 + ok(1).Thus, it explains why the regular random (k, s)-SAT instances are computationally harder than the uniform k-SAT generally.

关键词： Regular(k,s)-SAT Phase Transition 1RSB Cavity Approach Survey Propagation

作者: Jincheng Zhou Daoyun Xu Youjun Lu

作者单位: College of Computer Science and Technology,Guizhou University,Guiyang (550025),China;Department of M College of Computer Science and Technology,Guizhou University,Guiyang (550025),China

会议类型: 国内会议

会议名称: 2015全国理论计算机科学学术年会

会议地点: 金华

会议语种:英文

页码: 1-12

在线出版日期: 2015-10-30（万方平台首次上网日期，不代表论文的发表时间）