| 摘要: |
| 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问题 可满足临界 |
| DOI：10.13328/j.cnki.jos.006049 |
| 分类号:TP301 |
| 基金项目:国家自然科学基金（61762019，61862051） |
|
| Satisfiability Threshold of Strictly d-regular Random (3,2s)-SAT Problem for Fixed s |
|
WANG Yong-Ping1,2, XU Dao-Yun1
|
|
1.College of Computer Science and Technology, Guizhou University, Guiyang 550025, China;2.School of Mathematics and Statistics, Guizhou University of Finance and Economics, Guiyang 550025, China
|
| Abstract: |
| Generating random hard instances of the 3-CNF formula is an important factor in revealing the intractability of the 3-SAT problem and designing effective algorithms for satisfiability testing. Let k>2 and s>0 be integers, a k-CNF formula is a strictly regular (k,2s)-CNF one if the positive and negative occurrence number of every variable in the formula are s. On the basis of the strictly regular (k,2s)-CNF formula, the strictly d-regular (k,2s)-CNF formula is proposed in which the absolute value of the difference between positive and negative occurrence number of every variable is d. A novel model is constructed to generate the strictly d-regular random (k,2s)-CNF formula. The simulated experiments show that the strictly d-regular random (3,2s)-SAT problem has an SAT-UNSAT phase transition and a HARD-EASY phase transition when the parameter 5<s<11 is fixed, and that the latter is related to the former. Hence, the satisfiability threshold of the strictly d-regular random (3,2s)-SAT problem is studied when the parameter s is fixed. A lower bound of the satisfiability threshold is obtained by constructing a random experiment and using the first moment method. The subsequent simulated experiments verify well the lower bound proved. |
| Key words: 3-CNF formula generating random hard instances subclass with regular structure strictly d-regular random (3,2s)-SAT problem satisfiability threshold |
