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

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

⎛ kq ⎞ 2Ns
其中,σ是 k 和 q 的表达式.于是,由引理 2 可知,如果 ⎜ k − 1 ⎟ 是正整数,则:
1(1 q− ⎝ − ) ⎠ k
⎡ ⎛ kq ⎞ 2Ns ⎤ ⎡ ⎛ kq ⎞ 2Ns 2Ns ⎤
PY = ⎢ k − ⎜ 1 ⎟ ⎥ = PY = ⎢ k − ⎜ 1 ⎟ + 0 ⎥
−
−
−
−
⎣ ⎝ 1(1 q ) ⎠ k ⎦ ⎢ ⎣ ⎝ 1(1 q ) ⎠ k k ⎥ ⎦
⎡ ⎛ ⎜ kq − 1⎟ ⎞ 2Ns + 0 2Ns ⎤ 2Ns
⎢ ⎜ ⎝ 1(1 q ) k ⎟ ⎠ k k ⎥ ⎛ ⎜ k ⎞ ⎟
−−
⎢ z ⎜ ⎝ A () ( )z B z ⎟ ⎥ ⎠
= ⎢ ⎦ ⎥ ⎣ (6)
2Ns
A (1) (1) k
B
⎡ ⎛ − ⎞ 1 ⎤
1 ⎛ ⎢ 2Ns ⎞ ⎜ 2 ⎟ ⎥
+
= ⎢ 1 O ⎜ ⎜ ⎟ ⎟ ⎥
2σ π Ns ⎢ ⎝ ⎝ k ⎠ ⎜ ⎟ ⎠ ⎥ ⎣ ⎦
k
⎛ d ⎞ 2Ns ⎛ kq ⎞ 2Ns
进一步,如果 s + ⎜ N − = ⎜ ⎟ − 1 ⎟ ,则由公式(3)、公式(4)以及公式(6),可得 P(B|A)的一个渐
−
⎝ 2 ⎠ k 1 (1 q ) k ⎠ k
− ⎝
近表达式如下:
⎡ ⎛ − ⎞ 1 ⎤
1 ⎛ ⎢ 2Ns ⎞ ⎜ 2 ⎥ ⎟
+
(| )A =
PB ⎢ 1 O ⎜ ⎜ ⎟ ⎥ ⎟ (7)
2σ π Ns ⎢ ⎣ ⎝ ⎝ k ⎠ ⎜ ⎟ ⎥ ⎠ ⎦
k
综上,由公式(1)、公式(2)以及公式(7)可得如下定理.
定理 2. 设 F 是一个严格 d-正则随机(k,2s)-CNF 公式,σ F 是为 F 定义的特殊真值指派,而 q 是上述构造的随
q 2s d+
机实验中的概率值.如果 = ,则:
1(1 q− − ) k 4s
2Ns ⎡ ⎛ − ⎞ 1 ⎤
+
−
k
−
[1 (1 q ) ] k ⎢ 1 O ⎛ ⎜ 2Ns ⎞ ⎜ ⎟ 2 ⎟ ⎥
⎢ ⎜ ⎝ k ⎠ ⎜ ⎟ ⎟ ⎥
P ( F → F ) = ⎛ 2Ns ⎢ ⎝ ⎠ ⎦ ⎥ ⎣ ,
σ
π Ns ⎜ ⎛ ⎞ ⎜ s+ d ⎞ ⎟ N ⎛ ⎜ s− d ⎞ ⎟ N
2σ ⎜ ⎛ d ⎞ ⎟ q ⎝ ⎟ 2 ⎠ (1 q ) ⎝ 2 ⎠
−
k ⎜ s + ⎟ ⎜ N ⎟
⎝ 2 ⎠ ⎝ ⎠
⎛ − ⎞ 1 ⎛ − 1 − ⎞ 1
其中,N 是 F 的变量个数; O ⎛ ⎜ 2Ns ⎞ ⎜ ⎟ 2 ⎟ 表示存在常数 C>0,使得当 2Ns 足够大时,有 O ⎛ ⎜ 2Ns ⎞ ⎜ ⎟ 2 ≤ C ⎛ ⎟ ⎜ 2Ns ⎞ ⎟ 2 ;
⎜ ⎝ k ⎠ ⎜ ⎟ ⎟ k ⎜ ⎝ k ⎠ ⎜ ⎟ ⎝ ⎟ k ⎠
⎝ ⎠ ⎝ ⎠
而σ如公式(5)所示.
进一步,由 Stirling 近似可得定理 2 的如下推论.
推论 1. 设 F 是一个严格 d-正则随机(k,2s)-CNF 公式,σ F 是为 F 定义的特殊真值指派.如果 2s>d 并且方程
q = 2s d+
1(1 q− − ) k 4s 在(0,1)内存在根 q,则:
2Ns ⎡ ⎛ ⎛ − ⎞ 1 ⎤ d ⎞ N (2s d+ ) 1+ ⎛ d ⎞ N (2s d− ) 1+
−
+
k
−
[1 (1 q ) ] k ⎢ 1 O ⎜ 2Ns ⎞ ⎜ ⎟ 2 ⎟ k ⎛ ⎥ ⎜ 1+ ⎟ 2 ⎜ 1− ⎟ 2
⎢ ⎜ ⎝ k ⎠ ⎜ ⎟ ⎥ ⎝ ⎟ 2s ⎠ ⎝ 2s ⎠
P ( F → F ) = ⎢ ⎝ ⎛ d ⎞ ⎠ ⎦ ⎥ ⎣ ⎛ d ⎞ ,
σ
+
−
2 2Ns+ 1 σ q ⎜ ⎝ s+ 2 ⎠ ⎟ N (1 q ) ⎜ ⎝ s− 2 ⎠ ⎟ N [1 o (1)]
其中, lim (1)o = 0.
N →+∞
在下一小节,我们将研究严格 d-正则随机(3,2s)-SAT 问题的可满足临界.这意味着 k=3.因此,作为本小节的