给定含有N个布尔变元的合取范式(conjunctive normal form, 简称CNF)公式F, 可满足性问题(the satisfiability problem, 简称SAT问题)是指:是否存在一组对所有N个布尔变元的真值指派σ∈{0, 1}^N, 使得公式F的取值为TRUE.在SAT问题中, 限制每个子句长度为k的SAT问题称为k-SAT问题.该问题是判定由N个布尔变元{v₁, v₂, …, v_N}、M个子句{C₁, C₂, …, C_M}构成的合取范式F=C₁∧C₂∧…∧C_M的可满足性问题.其中, 每个子句C_i是由k个不同文字构成的析取范式C_i=(ℓ_i1∨ℓ_i2∨…∨ℓ_ik), 而文字ℓ是某个变元v或其否定形式¬v.当k≥3时, k-SAT问题是第一个被证明了的NP-complete问题^[1].因此在最坏情形下, 通常认为该问题没有有效的求解算法.此外, 研究者以SAT问题的NP-complete性质为种子, 利用多项式规约转换等技术, 已证明了大量的组合优化问题都是NP-complete问题^[2].因此, SAT问题, 特别是k-SAT问题, 仍然是当前理论计算机科学研究领域的一个核心问题.

随机k-SAT问题作为k-SAT问题的子集合, 其在k-SAT问题的典型计算复杂性研究中发挥着重要作用.在随机k-SAT问题中, 当变元规模N > > 1时, 一个重要的结构参数是子句个数M与变元个数N的比值α(也称约束密度).已有的理论和实验研究结果表明:该参数不仅能够影响到公式的判定难度, 还与公式的可满足性密切相关^{[3, 4]}.具体地, 当N > > 1时, 随着α的逐渐增大, 存在某个与k相关的临界值点(threshold point)α_s(k), 当随机公式F的约束密度满足α > α_s(k)时, 高概率地F是不可满足的, 而当随机公式F的约束密度满足α < α_s(k)时, 高概率地F是可满足的, 这种现象称为随机k-SAT问题的相变(phase transition)现象, 而临界值点α_s(k)被称为随机k-SAT问题的相变点.此外, 统计物理学中的一阶复本对称破缺(one step replica symmetry breaking, 简称1RSB)理论研究表明:在紧邻相变点α_s(k)前的某个位置, 随机k-SAT问题开始呈现簇集相变(clustering threshold)^[5], 从簇集相变点α_d(k)处开始, k-SAT问题的解空间将会突然分裂成数目众多的解集簇, 而这些解集簇之间相距甚远, 且在解集簇内部, 大量变元被凝固^[6-8].因此, 若仅仅通过翻转某个解集簇中一个解的少量变元的赋值, 不太可能将其转化为另一个解集簇中的解, 所以对于临界值点α_s(k)附近的实例, 现有的k-SAT求解算法均无法高效地求解, 即便是采用当前求解SAT问题最为有效的概观传播(survey propagation, 简称SP)算法^{[9, 10]}, 其在求解α_s(k)附近的k-CNF实例时也往往容易失效.另外, 在远离相变点α_s(k)的两侧, 绝大部分实例都是易于判定的.因此, 研究SAT问题的相变现象将有利于更深入地认识NP-complete问题的难解本质和设计更为有效的SAT问题求解算法.然而, 要找出该问题的精确相变点却是非常困难的.

当前已知的具有精确相变点的SAT问题主要包括:2-SAT^[11], Regular 2-SAT^[12], k-NAESAT^[13], k-XORSAT^[14]和Regular NAE-SAT^[15]等几种具有特殊规则结构的SAT子类.此外, 文献[16]采用1RSB理论预言随机k-SAT问题的相变点α_s(k)为α_s(k)=2^kln2-(ln2+1)/2+o_k(1).文献[17, 18]分别通过寻找随机k-SAT问题中解的聚类, 结合矩方法证明:当k充分大时, α_s(k)的渐近值与文献[16]的预测是相吻合的.

此外, 为使SAT问题的研究更为具体, 研究者通过对SAT问题的结构加以某些限制, 从而得到具有一定规则结构并保留NP-complete性质的公式子类.如:限制子句长度为k的k-SAT问题; 在k-SAT问题的基础上提出的每个变元至多出现σ次的k-SAT问题^[19]; 特别地, 文献[12]提出的每个变元恰好出现r次且每个变元正、负出现的期望次数至多相差1次的平衡(k, r)-SAT问题, 因其比一般k-SAT问题更难计算而受到研究者广泛关注^[20-24].在此基础上, 文献[20]研究了每个变元恰好出现r次且每个变元正、负出现次数至多相差1次的正则(k, r)-SAT问题, 并通过矩方法给出了该问题可满足临界的上下界.本文将在文献[20]的基础上, 给出该问题可满足临界值的改进上界.

第1节介绍相关工作的研究现状.第2节给出随机正则(k, r)-SAT问题的相关定义及严格随机正则(k, r)-SAT问题的实例产生模型.第3节通过构造特殊的独立随机实验, 结合一阶矩方法, 给出严格随机正则(k, r)-SAT问题可满足临界值的上界.由于严格正则情形与正则情形的可满足临界值近似相等, 从而得到了随机正则(k, r)-SAT问题可满足临界值的新上界.第4节通过数值分析结果验证所给上界的正确性.最后总结全文的工作.

1 随机正则(k, r)-SAT问题可满足临界的研究现状

当前, 在随机正则(k, r)-SAT问题的相变性质研究方面, 文献[12]首先证明了(3, r)-SAT问题的可满足临界值点α_rs(3)满足2.46≤α_rs(3)≤3.78.文献[21]在敌手可满足性问题(adversarial satisfiability problem)的研究中表明:针对随机(3, r)-CNF公式, 当r > 11时, 信念传播(belief propagation, 简称BP)算法在公式实例对应的因子图上收敛并会导致矛盾.即:当r > 11时, 随机(3, r)-CNF实例是高概率地不可满足的; 当r=10和r=11时, BP算法在其对应的因子图上不收敛且SP算法收敛于非平凡的固定点; 而当r < 10时, BP算法收敛于固定点, 即高概率地, 一个随机(3, r)-CNF实例是可满足的.因此, 随机正则(3, r)-SAT问题的相变点可能发生在r=10或r=11处.文献[22]通过引入一种特殊的树形结构, 并将正则因子图转换到树型结构上进行研究, 证明了若r为偶数时, 簇集相变点可能发生在r=8或者r=10处.进一步, 文献[23]首先通过将正则因子图转换成Cayley树, 然后再将其转换为相应的Bethe晶格(lattice)进行研究, 并证明了当r可以不取整数时, 簇集相变点α_rd(3)~3.23, 可满足相变点α_rs(3)~3.6.文献[24]结合概率生成函数的系数近似技术, 采用一阶矩方法严格证明了当r > 11时, 随机生成的正则(3, r)-CNF公式是高概率地不可满足的, 并且通过实验分析表明, 该问题的可满足相变点恰好发生在r=11处.另外, 文献[24]的实验研究还表明, 随机正则(3, r)-SAT问题在相变点r=11(α_rs(3)~3.6667)处的随机实例比通常的同变元规模的均匀随机3-SAT问题在相变点α_s(3)~4.2667处^[9]的随机实例更难求解.此外, 文献[20]通过一阶矩和二阶矩方法证明了存在某个常量k₀, 当k≥k₀时, 该问题的可满足临界值点α_rs(k)的上下界满足:2^kln2-(k+1) ln2/2-1≤α_rs(k)≤2^kln2, 其上下界之间的间隙为(k+1) ln2/2+1.

本文首先考虑随机正则(k, r)-SAT问题中每个变元出现次数r=2σ次且每个变元的正、负出现次数都恰为σ次的情形, 我们称这种情形下的k-SAT问题为严格随机正则(k, r)-SAT问题.通过构造特殊的独立随机实验, 结合一阶矩方法, 我们将证明存在某个常数k₁, 当k≥k₁时, 该问题可满足临界值的上界α_ru(k)为

${\alpha _{ru}}(k) = {2^k}\ln 2 - (k - 2)\ln 2/2.$

α_ru(k)=2^kln2-(k-2) ln2/2.

当严格随机正则(k, r)-CNF公式F的约束密度满足α_r≥α_ru(k)时, 高概率地F是不可满足的.进一步, 由于严格正则和正则情形的可满足临界值是近似相等的, 由此, 结合文献[20]所给出的此问题的下界, 我们得到了随机正则(k, r)-SAT问题可满足临界值点α_rs(k)的更为紧致的界, 即:2^kln2-(k+1) ln2/2-1≤α_rs(k)≤2^kln2-(k-2) ln2/2, 且上下界之间仅间隙一个常数1+3ln2/2.

2 问题描述与实例生成模型 2.1 基本概念

正则(k, r)-SAT问题^[20]是限制k-SAT问题中每个变元恰好出现r次, 且每个变元的正、负出现次数至多相差1次的k-SAT问题子类.为了便于相关的理论分析, 我们考虑每个变元恰好出现r=2σ(σ∈Z⁺)次且每个变元的正、负出现次数都恰为σ次的k-SAT问题, 并称其为严格正则(k, r)-SAT问题.由严格正则(k, r)-SAT问题的定义易知, 严格(k, r)-CNF公式的子句约束密度α_r满足α_r=M/N=r/k=2σ/k.严格随机正则(k, r)-CNF公式是均匀地从所有的严格正则(k, r)-CNF公式上选取的随机实例, 其对应的因子图^[25]可以用双正则二部图来表示, 其中, 二部图中的一侧由公式中的子句集构成, 而另一侧则由公式中的变元集构成.通常用矩形框表示子句节点, 用实心圆点来表示变元节点.若某个变元v_i在子句C_i中正出现, 则用实边连接v_i与C_i; 否则, 采用虚边连接.

图 1给出了严格正则(3, 6)-CNF公式F=C₁∧C₂∧…∧C₆的双正则二部图, 其中, C₁=(¬v₁∨v₂∨¬v₃), C₂=(¬v₁∨¬v₂∨v₃), C₃=(v₁∨¬v₂∨v₃), C₄=(¬v₁∨v₂∨v₃), C₅=(v₁∨¬v₂∨¬v₃), C₆=(v₁∨v₂∨¬v₃), 即:F中每个变元恰好出现6次, 且每个变元对应的正、负文字恰好出现3次.

2.2 严格随机正则(k, r)-SAT问题实例生成模型

对于给定的约束密度α、子句长度k和变元规模N, 一般的均匀随机k-SAT问题实例的生成模型是指:从所有$C_N^k \cdot {2^k}$个长度为k的可能子句中独立并且均匀地随机选取M=αN个子句构成的随机k-CNF公式.

在严格正则(k, r)-SAT问题中, 由于子句约束密度α_r=r/k, 因此我们需要给定的参数包括:变元出现次数r(r为正偶数)、子句长度k和变元规模N.在随机正则(k, r)-SAT问题实例生成模型中, 文献[24]所提出的生成随机(3, r)-SAT问题难解实例的SRR模型极易扩展为生成严格随机(k, r)-SAT问题实例模型, 但由于SRR模型为了防止在生成随机(3, r)-SAT问题难解实例过程中产生非法子句, 从而对实例的生成过程进行了一定的干预, 这将会增加我们分析随机公式的难度.因此, 本文采用文献[12]所提出的格局模型来生成严格随机正则(k, r)-CNF公式F, 具体生成算法如下:

Input:变元出现次数r, 子句长度k和变元规模N;

Step 1.依次对文字集L={v₁, ¬v₁, …, v_N, ¬v_N}中的每个正文字v_i和负文字¬v_i, 分别创建$s = \frac{r}{2}$个拷贝$v_i^1,v_i^2,...,v_i^s,\neg v_i^1,\neg v_i^2,...,\neg v_i^s$, 其中, i∈[M].

Step 2.对Step 1中的所有rN个文字随机生成一个投影π:Lx[σ]→[M]x[k].

Step 3.置第i个子句中的第j个文字F_ij=π(i, j), 其中, i∈[M], j∈[k].

Step 4.输出公式F.

事实上, 该模型所生成的随机公式中, 可能会出现某个变元在某个子句中出现多次的非法情形.此外, 该模型生成的随机公式还有可能产生重复子句, 但文献[12]的研究表明:存在常数δ > 0, 当N→∞时, Pr (F is legal)→δ, 且若合法的严格随机正则公式的可满足临界值存在, 则它与相应的格局公式的可满足临界值相同.因此, 为证明严格随机正则公式的可满足临界值的界, 我们仅需要证明相应的格局公式的可满足临界值的界即可.

3 随机正则(k, r)-SAT问题可满足临界

下面给出第3.1节中将用到的独立随机变元和的局部极限准则(the local limit law)^[26].

引理1(局部极限准则).令Z₁, …, Z_N是支撑ℤ_≥0上的N个独立随机变元, 且G(z)为其概率生成函数.令μ=E[Z_i], σ²=Var[Z_i], 如果G(z)是非周期的全函数且对所有的T₀ < α < T_∞, 当N→∞时, 有T_x=lim_z→xzG(z)/G'(z), 则有:

$\Pr \left[ {\sum\nolimits_{i = 1}^N {{Z_i}} = \alpha N} \right] = \frac{1}{{\sqrt {2\pi N\xi } }}G{(\zeta )^N} \cdot {\zeta ^{ - \alpha N - 1}}(1{\rm{ }} + o(1))$

(1)

其中, ζ和ξ为下面两个方程的解:

$\frac{{\zeta G'(\zeta )}}{{G(\zeta )}} = \alpha ,\xi = \frac{{{d^2}}}{{d{z^2}}}(\ln G(z) - \alpha \ln (z)){|_{z = \zeta }}$

(2)

3.1 严格随机正则(k, r)-SAT问题可满足临界值的上界

本节将构造一个特殊的独立随机实验, 并结合一阶矩方法来证明严格随机正则(k, r)-SAT问题可满足临界值的上界.

若Z为非负整数随机变量且其期望为E[Z], 则对任意的实数c > 0, 由马尔科夫不等式$\Pr (Z \ge c) \le \frac{{E[Z]}}{c}$知随机变元Z≥1的概率至多为E[Z], 此即一阶矩方法, 即:

$\Pr (Z \ge 1) \le E\left[ Z \right]$

(3)

若S表示严格随机正则(k, r)-CNF公式F的解空间, 则Ω=|S|为F的可满足解的总数目, 则由公式(3)有:

${\rm{Pr}}(F\;is\;{\rm{SAT}}) = {\rm{Pr}}(\mathit{\Omega } > 0) \le E[\mathit{\Omega }]$

(4)

对于F中变元集V={v₁, v₂, …, v_N}的任意指派σ(v₁, v₂, …, v_N), 令$\mathcal{A}$表示事件:指派σ(v₁, v₂, …, v_N)满足公式F; 令$\mathcal{B}$表示事件:指派τ=1=(1, 1, …, 1)满足公式F.因为严格正则公式中的每个正、负文字都恰好出现s次, 所以对变元集V的任何指派σ都会使得恰有$\frac{1}{2}$的文字取值为TRUE, 因此, 任何σ能成为一个可满足解的概率都是相同的, 即有Pr ($\mathcal{A}$)=Pr ($\mathcal{B}$)=Pr (F is SAT by σ)=Pr (F is SAT by 1)成立.由于N个变元的所有指派数共有2^N个, 所以结合公式(3)所给出的一阶矩方法有:

$\Pr (F\;{\rm{is}}\;{\rm{SAT}}) \le E[\mathit{\Omega } ] = \sum\nolimits_\sigma {\Pr (F\;{\rm{is}}\;{\rm{SAT}}\;{\rm{by}}\;\sigma )} = {2^N}\Pr (F\;{\rm{is}}\;{\rm{SAT}}\;{\rm{by}}\;1)$

(5)

为计算Pr (F is SAT by 1), 我们首先考虑这样的随机实验:在不考虑每个文字所对应的具体变元, 而仅仅区分每个文字的正、负情形下, 随机地分配正、负文字到所有M个子句中.由于在指派τ=1下所有正文字$v_i^1,v_i^2,...,v_i^s$的取值均为TRUE, 而所有负文字$\neg v_i^1,\neg v_i^2,...,\neg v_i^s$的取值均为FALSE, 其中, i∈[M].因此, F是可满足的当且仅当每个子句中至少存在一个正文字.

我们用独立随机变元F_ij(i∈[M], j∈[k])来表示第i个子句中的第j个文字的正、负取值, 使得F_ij∈{POSTTIVE, NEGATIVE}且Pr (F_ij=POSTTIVE)=p, 其中, F_ij=POSTTIVE表示第i个子句中的第j个文字为正文字, 相应地, F_ij=NEGATIVE表示第i个子句中的第j个文字为负文字.如果我们令函数f(s)为E[Ω]的熵密度, 即:

$f(s) = \frac{1}{N}\mathop {\lim }\limits_{N \to \infty } \ln E[\mathit{\Omega } ]$

(6)

则有如下的引理成立:

引理2.严格随机正则(k, r)-CNF公式中可满足解的期望数E[Ω]的熵密度f(s)为

$f(s) \sim \ln 2 + \frac{{2s}}{k}\ln (2p) - s\ln (4p(1 - p))$

(7)

其中, p=p(k)为方程(1-p)^k+2p-1=0的解.

证明:为计算f(s), 我们首先计算Pr (F is SAT by 1), 令指示变元${{\rm I}_{{F_{ij}} = {\rm{POSITIVE}}}}$定义为

${{\rm I}_{{F_{ij}} = {\rm{POSITIVE}}}} = \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ if }}{F_{ij}} = {\rm{POSITIVE}}}\\ {0,{\rm{ otherwise}}} \end{array}} \right.$

(8)

我们考虑如下两个事件:

$\mathcal{C}$:对严格随机正则公式F中的任何子句i∈[M], 存在某个j∈[k], 使得F_ij=POSTTIVE;

$\mathcal{D}$:严格随机正则公式F中的正文字总数恰为sN个, 即:$\sum {{{\rm I}_{{F_{ij}} = {\rm{POSITIVE}}}}} = \;sN.$

由事件$\mathcal{C}$和事件$\mathcal{D}$的定义得知, Pr (F is SAT by 1)的值与随机实验中事件$\mathcal{D}$发生下事件$\mathcal{C}$发生的概率是相等的, 因此有:

$\Pr (F\;{\rm{is}}\;{\rm{SAT}}\;{\rm{by}}\;1) = \Pr ({\cal C}|{\cal D}) = \frac{{\Pr ({\cal C}) \cdot \Pr ({\cal D}|{\cal C})}}{{\Pr ({\cal D})}}$

(9)

因为正则公式中的任何子句至少含有1个正文字的概率为1-(1-p)^k, 所以由事件$\mathcal{C}$的定义得知:M个子句中每个子句都至少含有1个正文字的概率Pr ($\mathcal{C}$)为

$\Pr (\mathcal{C}) = {(1 - {(1 - p)^k})^M}$

(10)

另外, 在事件$\mathcal{D}$中, 由于随机变量${{\rm I}_{{F_{ij}} = {\rm{POSITIVE}}}}$为伯努利随机变量, 因此, $\sum {{{\rm I}_{{F_{ij}} = {\rm{POSITIVE}}}}} $的取值服从B(2sN, p)的二项分布, 所以有:

$\Pr ({\cal D}) = \Pr \left( {\sum {{{\rm I}_{{F_{ij}} = POSITIVE}} = sN} } \right) = C_{2sN}^{sN}{p^{sN}}{(1 - p)^{sN}}$

(11)

由$\frac{M}{N} = \frac{{2s}}{k}$及Stirling公式$N! \sim \sqrt {2N\pi } \cdot {N^N}{{\rm{e}}^{ - N}}$有:

$\Pr ({\cal D}) = C_{2sN}^{sN}{p^{sN}}{(1 - p)^{sN}} = \frac{{(2sN)!}}{{(sN)!(sN)!}} \cdot {p^{sN}}{(1 - p)^{sN}}\; \sim \frac{{{2^{2sN}}}}{{\sqrt {sN\pi } }} \cdot {p^{sN}}{(1 - p)^{sN}}$

(12)

进一步, 我们采用具有M个随机变量的序列(Y_i)_i∈[M]来统计随机公式F中每个子句中的正文字数.由于在条件$\mathcal{C}$的限制下, 每个变量Y_i=j发生的概率与事件B(k, p)=j且j≥1发生的概率相等, 其中, B(k, p)表示参数为k, p的二项分布, 令$Y = \sum\nolimits_{i = 1}^M {{Y_i}} $, 则此时只需选择适当的p使得Y=E(Y|$\mathcal{C}$)=sN成立, 则有事件$\mathcal{D}$发生, 即:

$E(Y|{\cal C}) = M \cdot E[{Y_i}] = \;\frac{{2sN}}{k} \cdot \sum\limits_{j = 1}^k {\frac{{j \cdot \Pr \{ {Y_i} = j\} }}{{\Pr \{ {Y_i} \ge 1\} }}} \; = 2sN \cdot \frac{p}{{1 - {{(1 - p)}^k}}} = sN$

(13)

由公式(13)得知, p=p(k)应满足方程:

${(1 - p)^k} + 2p - 1 = 0$

(14)

对于M个独立随机变元的和$\sum\nolimits_{i = 1}^M {{Y_i}} $, 由引理1知, 存在常数δ_k(s) > 0, 使得:

$\Pr ({\cal D}|{\cal C}) = \Pr \left( {\sum\nolimits_{i = 1}^M {{Y_i}} = sN|{\cal C}} \right) \sim \frac{{{\delta _k}(s)}}{{\sqrt {2\pi N} }}$

(15)

结合公式(9)、公式(10)、公式(12)、公式(14)和公式(15)有:

$\begin{array}{l} f(s) = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}\ln E[\mathit{\Omega } ]\\ {\rm{ }} = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}({2^N} \cdot \Pr (F\;{\rm{is}}\;{\rm{SAT}}\;{\rm{by}}\;1))\\ \;\;\;\;\;\;\; = \mathop {\lim }\limits_{N \to \infty } \frac{1}{N}\left( {{2^N} \cdot \frac{{\Pr ({\cal C}) \cdot \Pr ({\cal D}|{\cal C})}}{{\Pr ({\cal D})}}} \right)\\ \;\;\;\;\;\;\; \sim \ln 2 + \frac{{2s}}{k}\ln (1 - {(1 - p)^k}) - s\ln (4p(1 - p))\\ \;\;\;\;\;\;\; = \ln 2 + \frac{{2s}}{k}\ln (2p) - s\ln (4p(1 - p)). \end{array}$

引理2证毕.

进一步, 对于每个固定的k≥3, 由公式(14)知p=p(k)为常数, 若能够证明函数f(s)是关于s的严格单调递减函数, 则当f(s)=0时, 便可得到严格随机正则(k, r)-SAT问题可满足临界值的上界α_ru(k), 由此, 我们给出如下的定理:

定理3.存在某个常数k₁, 当k≥k₁时, 若严格随机正则(k, r)-CNF公式F的约束密度${\alpha _r} = \frac{{2s}}{k}$满足${\alpha _r} > {\alpha _{ru}}(k) = {2^k}\ln 2 - \frac{{k - 2}}{2}\ln 2 + {o_k}(1)$时, 则随机公式F是高概率地不可满足的.

证明:由引理2得知$f'(s) = \frac{2}{k}\ln (2p) - \ln (4p(1 - p))$, 由p∈(0, 1)及p=p(k)满足方程(1-p)^k=1-2p易知0 < 1-2p < 1且$p < \frac{1}{2}$.令$t = \frac{1}{{1 - 2p}}$, 则公式(14)可化为${\left( {\frac{{t + 1}}{{2t}}} \right)^k} = \frac{1}{t}$, 即$k = \ln (t)/\ln \left( {\frac{{2t}}{{t + 1}}} \right)$, 下面我们证明f'(s) < 0.

由$\frac{2}{k}\ln (2p) - \ln (4p(1 - p)) = \frac{2}{k}\ln \left( {\frac{{2t - 2}}{{2t}}} \right) - \ln \left( {\frac{{{t^2} - 1}}{{{t^2}}}} \right)$, 即, 我们需要证明$\frac{{\ln (1 - {t^{ - 2}})}}{{\ln (1 - {t^{ - 1}})}} < \frac{2}{k}$成立.因此, 我们只需证明公式(16)和公式(17)成立即可:

$\frac{{\ln (1 - {t^{ - 2}})}}{{\ln (1 - {t^{ - 1}})}} < {t^{ - 1}}$

(16)

$k < 2t$

(17)

令x=t^-1, 则有0 < x < 1.由公式(16)得知ln (1-x²)-xln (1-x) > 0, 令g(x)=ln (1-x²)-xln (1-x), 则在x∈(0, 1)上有$g'(x) = \frac{x}{{1 + x}} - \ln (1 - x) > 0$成立, 所以g(x)是x∈(0, 1)上的严格单调递增函数.因此当x∈(0, 1)时, 有ln (1-x²)-xln (1-x) > g(0)=0成立, 即公式(16)成立.

进一步证明公式(17)也成立.由$t = \frac{1}{{1 - 2p}}$得知:为了证明$k = \frac{{\ln (t)}}{{\ln \left( {\frac{{2t}}{{t + 1}}} \right)}} < 2t$, 即$\frac{{\ln (1 - 2p)}}{{\ln (1 - p)}} < \frac{2}{{1 - 2p}}$成立, 我们只要证明(1-2p) ln (1-2p)-2ln (1-p) > 0即可.

令h(p)=(1-2p) ln (1-2p)-2ln (1-p), 则对任意的k≥3及$p < \frac{1}{2}$有(1-p)^k≤(1-p)³, 由(1-p)^k+2p-1=0得知1-2p≤(1-p)³, 所以有(1-p)³+2p-1≥0, 即$p \ge \frac{{3 - \sqrt 5 }}{2} > \frac{1}{4}$.因此, 结合$p < \frac{1}{2}$得知:

$h'(p) = (1 - 2p)\ln (1 - 2p) - 2\ln (1 - p) = - 2\ln (1 - 2p) - \frac{{2p}}{{1 - p}} > 0$

(18)

故h(p)是$p \in \left( {\frac{1}{4},\frac{1}{2}} \right)$上的严格单调递增函数, 因此有$h(p) > h\left( {\frac{1}{4}} \right) = \frac{{3\ln 2}}{2} > 0$, 即(1-2p) ln (1-2p)-2ln (1-p) > 0成立, 所以有f'(s) < 0.因此, f(s)是关于s的严格单调递减函数, 易知其有唯一的零点.

因为当k大于某个常数k₁时, 有p=p(k)~2^-1-2^-1-k, 则由$f(s) = \ln 2 + \frac{{2s}}{k}\ln (2p) - s\ln (4q(1 - p)) = 0$有:

${\alpha _{ru}}(k) = \frac{{2s}}{k} = \frac{{\ln 2}}{{\frac{k}{2}\ln (1 - {2^{ - 2k}}) - \ln (1 - {2^{ - k}})}}$

(19)

由$\ln (1 + x) = x - \frac{{{x^2}}}{2} + \frac{{{x^3}}}{3} + ... + {( - 1)^{n - 1}}\frac{{{x^n}}}{n} + o({x^n})$, 对公式(19)进行简化得${\alpha _{ru}}(k) \sim {2^k}\ln 2 - \frac{{k - 2}}{2}\ln 2 + {o_k}(1)$.因此, 当k较大且随机公式F满足${\alpha _r}(k) = \frac{{2s}}{k} > {\alpha _{ru}}(k)$时, 由于${\lim _{N \to \infty }}\frac{1}{N}\ln E[\mathit{\Omega } ] < 0$成立, 所以高概率地随机公式F是不可满足的.因此, 我们得到了α_rs(k)的一个上界, 即${\alpha _{rs}}(k) \le {\alpha _{ru}}(k) = {2^k}\ln 2 - \frac{{k - 2}}{2}\ln 2 + {o_k}(1)$成立.

定理3证毕.

3.2 随机正则(k, r)-SAT问题可满足的临界

随机正则(k, r)-SAT问题仅在r取奇数时有别于严格随机正则(k, r)-SAT问题, 而当r取奇数时, 随机正则(k, r)-CNF公式中每个变元的正、负出现次数恰好相差1次.由于α_rs(k)的确切值不一定恰好发生在r取奇数的情形, 另外, 即便这种情形发生, 此时的约束密度${\alpha _{rs}}(k) = \frac{r}{k}$的绝对误差仅为$\left| {\frac{{2\left\lfloor {r/2} \right\rfloor + 1}}{k} - \frac{{2\left\lfloor {r/2} \right\rfloor }}{k}} \right| = \frac{1}{k}$, 由于k较大时, $\frac{1}{k}$的值相对于整个临界值点α_rs(k)的值来说影响甚微, 因此可以认为严格正则和正则情形的可满足临界值是近似相等的.此外, 文献[21]中分别对r取偶数和奇数情形的推导表明:当k较大时, r取偶数或取值为一个与之相差1的奇数时, 其对应的可满足临界值是近似相等的.由此, 结合文献[20]中二阶矩方法给出的下界α_rl=2^kln2-$\frac{{k + 1}}{2}\ln 2 - 1$, 我们得到了随机正则(k, r)-SAT问题可满足临界值α_rs(k)的一个更紧致的界, 即:

${2^k}\ln 2 - \frac{{k + 1}}{2}\ln 2 - 1 \le {\alpha _{rs}}(k) \le {2^k}\ln 2 - \frac{{k - 2}}{2}\ln 2$

(20)

且上下界之间仅相差一个常数$1 + \frac{{3\ln 2}}{2}$.

4 数值结果

当k较小时, 我们可以直接通过计算得到引理2中p(k)的数值解, 并由f(s)=0来直接计算其相应的可满足临界值点的数值上界α_nru(k).表 1给出了3≤k≤11时, p(k)的数值解及近似解2^-1-2^-1-k、数值上界α_nru(k)、渐近上界α_ru(k)=2^kln2-(k-2) ln2/2以及渐近上界α_ru(k)与数值上界α_nru(k)的差α_ru(k)-α_nru(k).从表 1所给出的计算结果可知:数值解上界α_nru(k)与渐近上界α_ru(k)=2^kln2-(k-2) ln2/2的值较为接近, 且随着k不断增大(例如当k≥9时), 由于2^-1-2^-1-k能够较好地近似q(k)的数值结果, 因此, 2^kln2-(k-2) ln2/2也能很好地近似α_ru(k)的值.

当k=3时, 文献[23]证明了:如果r可以不取整数时, 随机正则(k, r)-SAT问题的临界值α_rs(3)~3.6.文献[24]预言:r取整数时, 该问题的临界值α_rs(3)~3.6667.而我们所给的数值上界结果α_nru(3)=3.7822已经非常接近α_rs(3)的值.此外, 文献[23]的研究表明:在接近相变点处的随机正则(k, r)-SAT问题实例, 其解空间的熵密度比接近相应相变点处同规模的均匀随机k-SAT问题实例的熵密度要小.由于均匀随机k-SAT问题在k较大时的可满足临界值点α_s(k)为2^kln2-(ln2+1)/2+o_k(1), 因此我们给出的随机正则(k, r)-SAT问题的可满足临界值的上界α_ru(k)明显在α_s(k)的左侧, 这也进一步从理论上解释了在相变点处的随机正则(k, r)-SAT问题实例为什么比在相应相变点处同规模的随机k-SAT问题实例更难满足.

5 结束语

描述解空间S大小Ω=|S|的一个重要统计物理学量是其熵密度lnΩ, 因此, 我们通过构造特殊的独立随机实验, 结合一阶矩方法, 采用lnE[Ω]来近似lnΩ并给出了随机正则(k, r)-SAT问题可满足临界值的一个新的上界.此外, 由统计物理中的1RSB理论可知^{[27, 28]}:当一个随机正则公式F的约束密度α_r满足α_r < α_rl(k)时, F的解空间被分解成了若干分割清晰的聚类, 每个聚类中包含着指数级可满足指派中的一小部分解, 此时有lnE[Ω]~ln[Ω]成立.相比之下, 当α_r > α_rl(k)时, 1RSB预言在接近相变点附近, 有限数量的聚类开始起主导作用, 即, 有限多个聚类覆盖了几乎整个解空间, 所以解空间S中, 解的分布的不均匀性将变得较为显著, 在这种情形下得到的lnE[Ω]的值将大于ln[Ω].因此在这个区域内, lnE[Ω]不能很好地近似ln[Ω], 所以本文通过一阶矩方法得到的上界值应该比α_rs(k)的实际值要稍微偏大一些.因此, 进一步的工作是如何利用统计物理学的相关知识, 找到α_rs(k)的确切值.