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

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

|{HH ∈ S 并且 H 的每个子句均包含 1-文字 }| ⎛ ⎜ s+ d ⎞ ⎟ N ⎛ ⎜ s− d ⎞ ⎟ N
|
F σ
(& F ) q ⎝ 2 ⎠ (1 q− ) ⎝ 2 ⎠
⎡ d ⎞ ⎤⎛ ⎡ d ⎞ ⎤⎛
⎜ s + ⎟ ⎢ N ⎥ ! s − ⎜ ⎟ ⎢ N ⎥ ! ( PA∩
( | ) ( )
P ( F → F ) = ⎝ 2 ⎠ ⎣ ⎦ ⎝ 2 ⎠ ⎣ ⎦ d ⎞ d ⎞ = ) B = P B A PA (1)
σ
()
| S | ⎛ ⎜ s+ ⎟ N ⎛ ⎜ s− ⎟ N PB ( P B)
F σ
−
(& F ) q ⎝ 2 ⎠ (1 q ) ⎝ 2 ⎠
⎡ d ⎞ ⎤⎛ ⎡ d ⎞ ⎤⎛
⎜ s + ⎟ ⎢ N ⎥ ! s − ⎜ ⎟ ⎢ N ⎥ !
⎝ 2 ⎠ ⎣ ⎦ ⎝ 2 ⎠ ⎣ ⎦
由事件 A 和 B 的含义可知:
⎛ 2Ns ⎛ ⎞
2Ns ⎜ ⎜ ⎟ s+ d ⎞ ⎟ N ⎛ ⎜ s− d ⎞ ⎟ N
−
k
( ) [1 (1 q
PA = − − ) ] k , ( )P B = ⎜ ⎛ d ⎞ ⎟ q ⎝ 2 ⎠ (1 q ) ⎝ 2 ⎠ (2)
⎜ s + ⎟ ⎜ N ⎟
⎝ 2 ⎠ ⎝ ⎠
注意到,可以由 Stirling 近似得到 P(B)的一个渐近表达式.因此,由公式(1)可知,得到 P(B|A)的一个渐近表达式成
为得到 P ( F → F ) 渐近表达式的关键.幸运的是,可以使用所谓的 Local Limit Law [19] 得到 P(B|A)的一个渐近表达式.
σ
为了使用 Local Limit Law,我们从文献[19]中摘录了一个定理作为下面的引理.
j
j
引理 2(large power and Gaussian forms) [19] . 设 ()A z = ∑ +∞ a z 和 ()B z = ∑ +∞ b z 是满足以下条件的两
j= 0 j j= 0 j
个解析函数:(1) A(z)和 B(z)在 0 处解析并且系数非负;(2) gcd{j|b j >0}=1;(3) B(0)≠0;(4) A(z)和 B(z)的收敛半径满
B′ (1) B′ ′ (1) B′ (1) ⎡ B′ (1)⎤ 2
足 1<R b ≤+∞,R b ≤R a .定义两个常数: μ ,σ = 2 = + − ⎢ ⎥ > 0 .设 N = μ n + x n ,其中,x 属于实数
B (1) B (1) B (1) ⎣ B (1) ⎦
n
N
n
域上某个有限区间.如果[z ](A(z)B(z) )表示 A(z)B(z) 的 N 次项系数,则:
x
⎛
1 [z N ]( ( ) ( ) ) = A z B z n 1 e − 2σ 2 2 ⎛ ⎜ 1 O n − ⎞ 1 2 ⎟ ⎞ , ⎟
+
⎜
π
B
A (1) (1) n σ 2 n ⎜ ⎜ ⎝ ⎝ ⎟ ⎠ ⎟ ⎠
⎛ − ⎞ 1 ⎛ − 1 − ⎞ 1
⎜
⎜
其中, On 2 ⎟ ⎟ 表示存在常数 C>0,使得当 n 足够大时,有 On 2 ⎟ ⎟ ≤ Cn 2 .
⎜
⎜
⎝ ⎠ ⎝ ⎠
设 X 0 =X 1 +X 2 +…+X k ≥1,其中,X 1 ,X 2 ,…,X k 是上述构造的随机实验中的前 k 重伯努利实验结果.对 X 0 独立重
2Ns
复观测 次.如果记各次实验结果之和为 X,则:
k
⎡ ⎛ d ⎞ ⎤
PX = ⎜⎢ s + ⎟ N = ⎥ P B (3)
(| ) A
⎝⎣ 2 ⎠ ⎦
⎡ ⎛ d ⎞ ⎤
其中,A 和 B 是公式(1)上方提及的两个事件.接下来,使用引理 2 得到 PX = ⎜⎢ s + ⎟ N 的一个渐近表达式.为了
⎥
⎝⎣ 2 ⎠ ⎦
2Ns
能够使用引理 2,令 Y 0 =X 0 −1,此时,如果对 Y 0 独立重复观测 次并记各次实验结果之和为 Y,则:
k
⎡ ⎛ d ⎞ 2Ns⎤ ⎡ ⎛ d ⎞ ⎤
PY = ⎜ ⎢ s + ⎟ N − ⎥ = P X = ⎜⎢ s + ⎟ N ⎥ (4)
⎝ ⎣ 2 ⎠ k ⎦ ⎝⎣ 2 ⎠ ⎦
⎡ ⎛ d ⎞ 2Ns ⎤
因此,接下来的工作就是利用引理 2 得到 PY = ⎜ ⎢ s + ⎟ N − ⎥ 的一个渐近表达式.
⎝ ⎣ 2 ⎠ k ⎦
k ⎛⎞
k
注意到,Y 0 的概率生成函数为 () x = f 1 k ∑ ⎜⎟ q i (1 q ) k i − x i− 1 .因此,可设 A(z)≡1,B(z)≡f(z).容易看出,
−
−
−
1(1 q ) i= ⎝⎠
1 i
kq
A(z)和 B(z)满足引理 2 条件.经过计算可得 μ = − 1.由 f(x)的系数及文献[20]可知:
−
−
1(1 q ) k
2
σ >0 (5)