取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

摘要：

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k＞2和s＞0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则(k,2s)-CNF公式.受严格正则(k,2s)-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则(k,2s)-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机(k,2s)-CNF公式.取定整数5＜s＜11,模拟实验显示,严格d-正则随机(3,2s)-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机(3,2s)-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机(3,2s)-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.

关键词：3-CNF公式;随机难解实例生成;正则子类;严格d-正则随机(3,2s)-SAT问题;可满足临界

所属期刊栏目：32

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

资助基金：国家自然科学基金61762019,61862051

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

页数：共13页

页码：2629-2641