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

Satisfiability Threshold of Strictly d-regular Random(3,2s)-SAT Problem for Fixed s

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取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.

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.