Page 14 - 《软件学报》2021年第9期

2638 Journal of Software 软件学报 Vol.32, No.9, September 2021

⎛ 8s ⎞ 4s ⎛ 4s ⎞
(2 −
gs 2) = ln 2 + ⎜ − 1 ln(2s − 1) − ln s − ⎜ − 1 ln[3(2s − 1) − (2s − 1)(2s + 3)] ln[ (2s− − 1)(2s + 3) − (2s − 1)].
⎟
⎟
⎝ 3 ⎠ 3 ⎝ 3 ⎠
为此,考虑定义在[1,+∞)上的函数:
⎛ 8x ⎞ 4x ⎛ 4x ⎞
( ) =
Hx ln2 + ⎜ − 1 ln(2x − 1) − ln x − ⎜ − 1 ln[3(2x − 1) − (2x − 1)(2x + 3)] ln[ (2x− − 1)(2x + 3) − (2x − 1)].
⎟
⎟
⎝ 3 ⎠ 3 ⎝ 3 ⎠
4 (2x − 1) 2
经过计算和整理可得, Hx = ln .
′
()
3 3 (2 − 1) x (2x − 1)(2x + 3)
−
xx
注意到, (2 − x 1) − 2 3 (2 −x x 1) + x (2 − x 1)(2 + x 3) = 2 − x 1(x 2 + x 3 (− + x 1) 2 − x 1) > 0.
1 8 1 11 5 5+
又注意到, H (1) = ln = ln > 0.
3 (3 − 5)( 1− + 5) 3 3 4
于是,由 s≥1 可知,g(2s−2)=H(s)>0,即结论(2)得证. □
设 g(x)是引理 4 中定义的函数.由引理 5 可知,研究什么条件使得 g(x)<0,还需考虑 g(x)在定义域内的单调性.
为此,有下述引理.
引理 6. 引理 4 中定义的函数 g(x)在定义域内单调递增.
证明:经过计算可得:
x
′
( ) =
gx 1 ln (2s + x − )( (2s + ) x + (2s + x )(10s − 3 )) = 1 ln 2(2s + ) x .
2 (2s − x )(3(2s + ) x − (2s + x )(10s − 3 )) 2 3x − 2s + (2s + x )(10s − 3 ) x
x
注意到:
2(2s + ) x ⎡ 6s −− (2s + x )(10s − 3 ) x ⎤ 6s −− (2s + x )(10s − 3 ) x
x
x
ln = ln 1+ ⎢ > > ⎥ 0.
3x − 2s + (2s + x )(10s − 3 )x 3x −⎢ 2s + (2s + x )(10s − 3 )x ⎥ ⎣ ⎦ 2(2s + ) x
因此,g′(x)>0.于是,结论得证.引理 6 证毕. □
现在,根据引理 4~引理 6 并结合一阶矩方法,可得到严格 d-正则随机(3,2s)-SAT 问题在 s 取定时可满足临界
值的一个下界如下.
定理 3. 设 F 是一个严格 d-正则随机(3,2s)-CNF 公式.如果 s≥6 并且 2s>d,则当 d<d 0 并且 N 足够大时,公式
F 是高概率不可满足的,其中,d 0 是引理 4 中定义的函数 g(x)在区间(0,2s−2)内的唯一零点.
注意到,F 是一个严格 d-正则随机(3,2s)-CNF 公式.因此,可以为 F 定义特殊真值指派σ F .由σ F 的定义可知:
当 2s=d 时,σ F 是 F 的解,即 F 是可满足的.因此,在定理 3 中加入了条件 2s>d.
证明:由引理 5 和引理 6 可知:当 s≥6 时,引理 4 中定义的函数 g(x)在区间(0,2s−2)内存在唯一零点 d 0 .设Ω
ln [ ]ΩE
是 F 解的个数,则由 2s>d、引理 4、引理 6 以及 d<d 0 可知, lim ≤ gd ( ) = ,从而 lim ln [ ]E Ω =−∞
0
.
( ) < gd
N →+∞ N 0 N →+∞
于是,由本小节开始时的讨论可知:当 d<d 0 并且 N 足够大时,公式 F 是高概率不可满足的.定理 3 证毕. □
定理 3 的证明给出了唯一零点 d 0 的存在性.由函数 g(x)表达式的复杂性可知,不太容易给出 d 0 的表达式.
作为替代,表 1 给出了当 s=10,20,…,100 时 d 0 的数值解.注意:对于任意取定的 s,求出 d 0 的数值解是容易的.
Table 1 Numerial solutions of the null point d 0 when s∈{10,20,…,100}
表 1 当 s=10,20,…,100 时,唯一零点 d 0 的数值解
s d 0 s d 0
10 2.803 7 60 59.682 4
20 11.831 0 70 72.972 7
30 22.603 8 80 86.574 7
40 34.358 5 90 100.437 7
50 46.775 6 100 114.523 4
3 模拟实验

根据定理 3 的条件 d<d 0 ,结合表 1,我们分别选择了 s=20,30,40,50,60;同时,根据条件 N 足够大,我们分别选