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

来源：软件学报杂志2016年第12期北京时间：

作者：周锦程,许道云,卢友军

单位：周锦程，贵州大学 计算机科学与技术学院, 贵州 贵阳 550025;黔南民族师范学院 数学与统计学院, 贵州 都匀 55800011,许道云，贵州大学 计算机科学与技术学院, 贵州 贵阳 55002502,卢友军，贵州大学 计算机科学与技术学院, 贵州 贵阳 55002503

摘要：研究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问题;可满足临界值;相变现象;计算复杂性

基金资助：国家自然科学基金（61262006，61463044，61462001）；贵州省科技厅联合基金（LKQS201313）