随机正则(k,r)-SAT问题的可满足临界

摘要：

研究k-SAT问题实例中每个变元恰好出现r=2s次,且每个变元对应的正、负文字都出现s次的严格随机正则(k,r)-SAT问题.通过构造一个特殊的独立随机实验,结合一阶矩方法,给出了严格随机正则(k,r)-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等闺此得到了随机正则(k,r)-SAT问题可满足临界值的新上界.该上界不仅小于当前已有的随机正则(k,r)-SAT问题的可满足临界值上界,而且还小于一般的随机k-SAT问题的可满足临界值.因此,这也从理论上解释了在相变点处的随机正则(k,r)-SAT问题实例通常比在相应相变点处同规模的随机k-SAT问题实例更难满足的原因.最后,数值分析结果验证了所给上界的正确性.

关键词：随机正则(k、r)-SAT问题、可满足临界值、相变现象、计算复杂性

所属期刊栏目：27

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61262006,61463044,61462001;贵州省科技厅联合基金LKQS201313National Natural Science Foundation of China61262006,61463044,61462001;Science and Technology Foundation of Guizhou Province of ChinaLKQS201313

在线出版日期：2017-01-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2985-2993