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

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

为方便起见,记为 P (σ→F) .
设 F 是一个严格 d-正则随机(k,2s)-CNF 公式.对于每一个 x∈{x 1 ,x 2 ,…,x N },若 x 在 F 中的正出现次数不小于
负出现次数,令σ F (x)=1;否则,令σ F (x)=0.显然,σ F 是为 F 定义的特殊真值指派.作为下一小节使用一阶矩方法的准
备,我们给出了概率值 P ( F → F ) 的两个性质.
σ
N
(1) 对于任意的真值指派σ∈{0,1} ,都有 P (σ F ) ≤ P ( F → σ → F ) ;
(2) 通过构造一个特殊随机实验,可得到 P ( F → F ) 的一个渐近表达式.
σ
首先,给出得到 P ( F → F ) 最大性性质的一个引理.
σ
N
引理 1. 设 F 是一个严格 d-正则随机(k,2s)-CNF 公式,σ∈{0,1} 是一个真值指派.如果存在真值指派τ∈
N
{0,1} ,使得|A (F&σ) |≤|A (F&τ) |,则 P (σ→F) ≤P (τ→F) .
证明:不妨设 F 含 M 个子句,则|A (F&σ) ∪B (F&σ) |=kM=|A (F&τ) ∪B (F&τ) |.于是可设:
A (F&σ) ={t 1 ,t 2 ,…,t a },B (F&σ) ={t a+1 ,t a+2 ,…,t kM },A (F&τ) ={T 1 ,T 2 ,…,T a+b },B (F&τ) ={T a+b+1 ,T a+b+2 ,…,T kM },
其中,a 和 b 是使得 a+b≤kM 的非负整数.设 H 是 S (F&σ) 中任意一个公式.如果对于任意的 i∈[M]和 j∈[k],l ij 表示
H 第 i 个子句中的第 j 个文字,则 l 11 ,l 12 ,…,l 1k ,l 21 ,l 22 ,…,l 2k ,…,l M1 ,l M2 ,…,l Mk 是多重集 A (F&σ) ∪B (F&σ) 的一个置换.于是,
由对 A (F&σ) 和 B (F&σ) 的假设可知,该置换还可表示如下:
t 1′ ,t 2′ ,…,t k′ ,t [(2−1)k+1]′ ,t [(2−1)k+2]′ ,…,t (2k)′ ,…,t [(M−1)k+1]′ ,t [(M−1)k+2]′ ,…,t (Mk)′ ,
其中,下标全体组成的集合恰好是[kM].如果对于任意的 i∈[M]和 j∈[k],令 L ij =T [(i−1)k+j]′ ,则如下的格局公式:
(L 11 ∨L 12 ∨…∨L 1k )∧(L 21 ∨L 22 ∨…∨L 2k )∧…∧(L M1 ∨L M2 ∨…∨L Mk )
必定属于 S (F&τ) .进一步,如果令该格局公式为 f(H),则容易证明,f 是 S (F&σ) 和 S (F&τ) 之间的双射函数.设多重集 S 1 =
{G|G∈S (F&σ) 并且 G 的每个子句均包含 1-文字},S 2 ={H|H∈S (F&τ) 并且 H 的每个子句均包含 1-文字},显然,对于任
意的 G 0 ∈S 1 都有:G 0 的每个子句均包含 A (F&σ) 中的文字.因此,由双射函数 f 的定义可知,f(G 0 )的每个子句均包含
A (F&τ) 中的文字,即 f(G 0 )∈S 2 .进一步,由双射函数 f 是从 S 1 到 S 2 的单射可知,|S 1 |≤|S 2 |.最后,由|S (F&σ) |=(kM)!=|S (F&τ) |
可知,P (σ→F) ≤P (τ→F) .引理 1 证毕. □
设 F 是一个严格 d-正则随机(k,2s)-CNF 公式,σ F 是为 F 定义的特殊真值指派.由σ F 的定义可知:对于任意的
N
真值指派σ∈{0,1} ,都有 | A (& )F σ |≤ | A ( & F ) | .于是,由引理 1 可得如下定理.
F σ
定理 1. 设 F 是一个严格 d-正则随机(k,2s)-CNF 公式,σ F 是为 F 定义的特殊真值指派,则对于任意的真值指
N
派σ∈{0,1} ,都有 P (σ F ) ≤ P ( F → σ → F ) .
定理 1 给出了 P ( F → F ) 的最大性性质.因此,本小节余下的主要内容将是得到 P ( F → F ) 的一个渐近表达式.注
σ
σ
2Ns ⎛ d ⎞ ⎛ d ⎞
意到,F 包含 2Ns 个文字和 个子句.又注意到,F 的由σ F 决定的 1-文字有 s + ⎟ N 个,0-文字有 s − ⎟ N 个.
⎜
⎜
k ⎝ 2 ⎠ ⎝ 2 ⎠
2Ns 2Ns
因此,可先构造一个特殊随机实验来得到 P ( F → F ) 的一个定性表达式.假设有编号分别为 1,2,…, k 的 k 个
σ
盒子,其中,每个盒子均包含编号分别为 1,2,…,k 的 k 个格子.如下进行随机实验:首先,按编号的自然顺序将盒子
排序;其次,以概率 0<q<1 进行 2Ns 重伯努利实验,并记实验结果分别为
X 1 ,X 2 ,…,X k ,X k+1 ,X k+2 ,…,X 2k ,…,X 2Ns−k+1 ,X 2Ns−k+2 ,…,X 2Ns ;
⎡ 2Ns ⎤
最后,对于任意的 i∈ ⎢ ⎥ 和 j∈[k],当 X (i−1)k+j =1 时,将第 i 个盒子编号为 j 的格子贴上标签 label-1,否则贴上标
⎣ k ⎦
⎛ d ⎞
签 label-0.记在实验中每个盒子均包含被贴上标签 label-1 的格子为事件 A,并记标签 label-1 被贴 s + ⎟ N 次为
⎜
⎝ 2 ⎠
⎡ 2Ns ⎤
事件 B.由 0<q<1 可知,事件 B 发生的概率 P(B)>0.注意到:对于任意的 i∈ ⎢ ⎥ 和 j∈[k],将第 i 个盒子编号为 j
⎣ k ⎦
的格子贴上标签 label-1 可看作在公式的第 i 个子句的第 j 个位置放置 1-文字.因此,由 0<q<1 可知: