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

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

q 2s d+
结束,经过简单计算,给出 k=3 和 2s>d 时方程 = 在(0,1)内的根 q 如下.
−
−
1(1 q ) k 4s
q 2s d+
引理 3. 设 F 是一个严格 d-正则随机(3,2s)-CNF 公式.如果 2s>d,则方程 = 在(0,1)内存在唯
1(1 q− − ) 3 4s
3(2s d+ ) − (2s d+ )(10s − 3 )d
一根: q = .
2(2sd+ )
设 F 是一个严格 d-正则随机(k,2s)-CNF 公式,σ F 是为 F 定义的特殊真值指派.显然,定理 1 和推论 1 分别给
出了 P ( F → F ) 的最大性性质和一个渐近表达式.这两个结论是下一小节使用一阶矩方法得到严格 d-正则随机
σ
(3,2s)-SAT 问题在 s 取定时可满足临界值下界的基础.
2.2 可满足临界
设 F 是一个严格 d-正则随机(k,2s)-CNF 公式,Ω是 F 的解的个数.由 Markov 不等式可知,P(F 是可满足的)=
P(Ω≥1)≤E[Ω].于是,当 E[Ω]<<1 时,公式 F 是高概率不可满足的.注意到:如果 lim ln [ ]E Ω =−∞ ,则当 N 足够大
N →+∞
时,E[Ω]<<1.因此,如果 lim ln [ ]E Ω = −∞ ,则当 N 足够大时,公式 F 是高概率不可满足的.基于这一结论,我们给出
N →+∞
了下面 3 个引理,并由此得到了严格 d-正则随机(3,2s)-SAT 问题在 s 取定时可满足临界值的一个下界.
ln [ ]E Ω ln [ ]E Ω
注意到:如果 lim < 0 ,则 lim ln [ ]E Ω =−∞ .因此,先给出下面的关于 lim 的引理.
N →+∞ N N →+∞ N →+∞ N
ln [ ]ΩE
引理 4. 设 F 是一个严格 d-正则随机(3,2s)-CNF 公式,Ω是 F 解的个数.如果 2s>d,则 lim ≤ g ( ) d ,
N →+∞ N
其中,
⎛ 4s ⎞ ⎛ 5s x ⎞ 4s ⎛ x ⎞ ⎛ s x ⎞
g ( ) x = ⎜ 1− ⎟ ln2 + ⎜ + ⎟ ln(2s + ) x − ln s + ⎜ s − ⎟ ln(2s − ) x − ⎜ + ⎟ ln[3(2s + ) x − (2s + x )(10s − 3 )]− x
⎝ 3 ⎠ ⎝ 3 2 ⎠ 3 ⎝ 2 ⎠ ⎝ 3 2 ⎠
⎛ x ⎞
s − ⎜ ⎟ ln[ (2s + − ) x + (2s + x )(10s − 3 )],x x∈ [0,2s − 2].
⎝ 2 ⎠
N
证明:由定理 1 可知, []E Ω ≤ 2 P ( F → F ) .于是,由 2s>d、引理 3 和推论 1 可知:
σ
ln [ ]E Ω ⎛ ln P ( F → ) ⎞ 2s ⎛ d ⎞ ⎛ d ⎞
σ
−
−
−
lim ≤ lim ln 2 + F = ⎟ (1 2 )ln2s + ln[1 (1 q ) ]+ 3 ⎜ s + ⎟ ln 1+ ⎜ ⎟ +
⎜
N →+∞ N N →+∞ ⎝ N ⎠ 3 ⎝ 2 ⎠ ⎝ 2s ⎠
⎛ d ⎞ ⎛ d ⎞ ⎛ d ⎞ ⎛ d ⎞
s − ⎜ ⎟ ln 1− ⎜ ⎟ − ⎜ s + ⎟ ln q − ⎜ s − ⎟ ln(1 q ).
−
⎝ 2 ⎠ ⎝ 2s ⎠ ⎝ 2 ⎠ ⎝ 2 ⎠
进一步,由引理 3 可知,该引理成立. □
ln [ ]E Ω
设 g(x)和 d 如引理 4 所示.如果 g(d)<0,则由引理 4 可知, lim < 0 .因此,需要研究什么条件使得
N →+∞ N
g(x)<0.注意到,x∈[0,2s−2].为此,我们研究了 g(x)在 0 处和 2s−2 处的取值情况.
引理 5. 设 g(x)是引理 4 中定义的函数,则:(1) 当 s≥6 时,g(0)<0;(2) g(2s−2)>0.
s
证明:先来证明结论(1).经过计算可得, (0)g = ln2 − ln(3 − 5) s− ln( 1− + 5) .为此,考虑函数:
3
x
( ) =
hx ln 2 − ln(3 − 5) x− ln( 1− + 5), x∈ [1,+ ∞ ).
3
注意到:
′
+
×
<
( ) =
−
−
+
hx − 1 ln[(3 − 5)( 1+ − 5) ] = 3 − 1 ln( 88 40 5) < − 1 ln( 88 40 2.23) = − 1 ln1.2 0,
3 3 3 3
(3 − 5) ( 1− 2 + 5) 6
2
h (6) =− ln =− ln[32( 11 5 5) ]− + 2 <− ln[5.6 ( 11 5 2.236) ]− + × 2 = − 2ln1.008 0.<
2
因此,由 s≥6 可知,结论(1)成立.再来证明结论(2).经过计算可得: