王永平,许道云

1(贵州大学 计算机科学与技术学院,贵州 贵阳 5 50025)

2(贵州财经大学 数统学院,贵州 贵阳 550 025)

Fig.1 Ratio of satisfiable instances when N=180 and s∈{1,2,…,10}图1 当N=180 而s=1,2,…,10 时的可满足实例占比

Fig.2 Average time in seconds for solving an instance when N=180 and s∈{1,2,…,10}图2 当N=180 而s=1,2,…,10 时,求解一个实例的平均时间(s)

取定整数5

1 SDRRK2S 模型

2 可满足临界分析

本节主要使用文献[13]的方法研究严格d-正则随机(3,2s)-SAT 问题在s取定时的可满足临界.这一过程主要分成两步:一是通过构造特殊随机实验得到一个特殊真值指派是一个严格d-正则随机(k,2s)-CNF 公式解的概率的渐近表达式;二是使用一阶矩方法得到严格d-正则随机(3,2s)-SAT 问题在s取定时可满足临界值的下界.

2.1 相关准备

设F是一个严格d-正则随机(k,2s)-CNF 公式.如果F的文字全体组成的多重集是L,则由SDRRK2S 模型可知,L可作为该模型Step 2 中的多重集A.由SDRRK2S 模型还可知,该模型可由L生成(2Ns)!个公式.因此,该(2Ns)!个公式中可满足的公式占比即为F是可满足的概率.如果F的文字全体组成的多重集是L′,则由SDRRK2S 模型可知,此时F是可满足的概率与F的文字全体组成的多重集是L时相应的概率相等.因此在本节中,约定F的文字全体组成的多重集是某个取定的集合.

设F是一个严格d-正则随机(k,2s)-CNF 公式.注意到,F是否可满足取决于是否存在作为F解的真值指派.因此,可考虑使用真值指派和公式共同描述该公式可满足的可能性.设l是F的一个文字,σ∈{0,1}N是一个真值指派.如果σ(l)=1,则称l是公式F的由σ决定的1-文字;否则是公式F的由σ决定的0-文字.在不致混淆的情况下,简称l是1-文字或0-文字.设A(F&σ)是1-文字全体组成的多重集,而B(F&σ)是0-文字全体组成的多……