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

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

d d
每个变量均出现 2s 次,并且正负出现次数之差的绝对值均为 d.这意味着,每个变量均只能正出现 s + 或 s −
2 2
次.因此,在 SDRRK2S 模型中,借鉴了文献[11]的模型当 s 是奇数时的情形来确定每个变量的正出现次数:每个变
d d
量均出现 2s 次,但以相等的概率正出现 s + 或 s − 次.另一方面,当 k=3 并且比值α>3.7822 时,文献[13,17,18]
2 2
的模型生成的公式均是高概率不可满足的;但文献[13]的模型由文字多重集得到随机公式的方式更便于计数.
因此,在 SDRRK2S 模型中,采用了由文字多重集的一个置换得到一个随机公式的方式.
设整数 k>2,s>0,N>0 以及 d∈{0,2,…,2s},则 SDRRK2S 模型可叙述如下.
Input:子句长度 k,变量出现次数 2s,变量个数 N,变量正负出现次数之差的绝对值 d,其中,2Ns 是 k 的倍数.
Step 1. 对于每一个 i∈[N],以随机方式生成多重集 A i ={x i ,…,x i ,¬x i ,…,¬x i },其中,A i 中有 2s 个元素,而且 x i 的
d d
个数以相等的概率取 s + 或 s − .
2 2
N
Step 2. 记多重集 A = ∪ A ,并均匀地从 A 的置换全体中选择一个置换.不妨设该置换为
i
i= 1
a 1 ,a 2 ,…,a k ,a k+1 ,a k+2 ,…,a 2k ,…,a 2Ns-k+1 ,a 2Ns-k+2 ,…,a 2Ns .
Step 3. 根据 Step 2 中的置换生成公式 F 如下:
F=(a 1 ∨a 2 ∨…∨a k )∧(a k+1 ∨a k+2 ∨…∨a 2k )∧…∧(a 2Ns-k+1 ∨a 2Ns-k+2 ∨…∨a 2Ns ).
Output:输出公式 F.
注意,SDRRK2S 模型生成的公式是含有 N 个布尔变量的格局公式.因此,该类公式可能包含非法子句.实际
上,由文献[17]可知:当 k=3 时,SDRRK2S 模型以正概率输出简单公式.此外,由文献[17]还可知:当 k=3 并且
SDRRK2S 模型生成的格局公式存在 SAT-UNSAT 相变现象时,相应的简单公式也存在相同的相变.再加上本文
关注的是严格 d-正则随机(3,2s)-SAT 问题在 s 取定时的可满足临界,因此我们没有在 SDRRK2S 模型中加入简
单公式的限制.
2 可满足临界分析

本节主要使用文献[13]的方法研究严格 d-正则随机(3,2s)-SAT 问题在 s 取定时的可满足临界.这一过程主
要分成两步:一是通过构造特殊随机实验得到一个特殊真值指派是一个严格 d-正则随机(k,2s)-CNF 公式解的概
率的渐近表达式;二是使用一阶矩方法得到严格 d-正则随机(3,2s)-SAT 问题在 s 取定时可满足临界值的下界.
2.1 相关准备
设 F 是一个严格 d-正则随机(k,2s)-CNF 公式.如果 F 的文字全体组成的多重集是 L,则由 SDRRK2S 模型可
知,L 可作为该模型 Step 2 中的多重集 A.由 SDRRK2S 模型还可知,该模型可由 L 生成(2Ns)!个公式.因此,该
(2Ns)!个公式中可满足的公式占比即为 F 是可满足的概率.如果 F 的文字全体组成的多重集是 L′,则由
SDRRK2S 模型可知,此时 F 是可满足的概率与 F 的文字全体组成的多重集是 L 时相应的概率相等.因此在本节
中,约定 F 的文字全体组成的多重集是某个取定的集合.
设 F 是一个严格 d-正则随机(k,2s)-CNF 公式.注意到,F 是否可满足取决于是否存在作为 F 解的真值指派.
N
因此,可考虑使用真值指派和公式共同描述该公式可满足的可能性.设 l 是 F 的一个文字,σ∈{0,1} 是一个真值
指派.如果σ(l)=1,则称 l 是公式 F 的由σ决定的 1-文字;否则是公式 F 的由σ决定的 0-文字.在不致混淆的情况下,
简称 l 是 1-文字或 0-文字.设 A (F&σ) 是 1-文字全体组成的多重集,而 B (F&σ) 是 0-文字全体组成的多重集.进一步,
设 S (F&σ) 是 SDRRK2S 模型由多重集 A (F&σ) ∪B (F&σ) 生成的公式全体组成的多重集.于是,真值指派σ是公式 F 解的
概率如下:
|{HH ∈ S (& )F σ 并且 H 的每个子句均包含 1-文字 }| .
|
| S (& )F σ |