A novel weighting scheme for random k-SAT

作者：Liu, Jun; Xu, Ke^*

来源：Science China Information Sciences, 2016, 59(9): 092101.

DOI：10.1007/s11432-016-5526-8

• computational complexity
• satisfiability
• phase transition
• second moment method
• weighting scheme

Consider a random k-conjunctive normal form F-k(n, rn) with n variables and rn clauses. We prove that if the probability that the formula F-k(n, rn) is satisfiable tends to 0 as n -> 8, then r >= 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.

• 出版日期2016-9
• 单位软件开发环境国家重点实验室; 北京航空航天大学