均衡正则恰当(2s，k)-SAT问题是指：是否存在一组变元指派，使得(2s，k)-SAT实例的每个子句恰好有一个文字为真．显然，均衡正则恰当(2s，k)-SAT问题仍然是NP难问题．目前，该问题的可满足性严格相变还不清楚．须要寻找用以度量该问题可满足性相变的新参数．研究人员对几个类似的问题做了深入研究，并取得了可满足性相变的一些重要的研究结果．文献[1]研究了随机正则(d，k)-NAE-SAT问题的可满足性相变，得到一个关于参数d的相变控制参数．在不考虑d的取值下，文献[2]给出了3NAE-SAT问题的相变，文献[3]给出了kNAE-SAT问题的相变．对于恰当可满足性问题，文献[2]给出了1-in-k-SAT问题(即在某个真值指派下每个子句恰好有一个文字为真)的可满足性相变，文献[4]给出了2-in-4-SAT问题可满足性相变．在1-in-k-SAT问题中，假设每个公式不含负文字，该问题本质上变为一个恰当覆盖问题，文献[5]给出了恰当覆盖问题的可满足性相变．在恰当覆盖问题中，若每个变元在公式中出现的次数相等，则称恰当覆盖问题为正则的，文献[6]给出了正则恰当覆盖问题的相变．上述研究结果对于分析均衡正则恰当(2s，k)-SAT问题的可满足性相变具有十分重要的借鉴意义．上述关于相变的证明技术，主要是基于一阶矩方法和二阶矩方法[7-15]．然而，一个重要的问题是当使用二阶矩方法时，须要对问题的解空间结构进行刻画，这是非常困难的[4]，因此还有大量的开放问题未获得严格的相变点．事实上，随机正则SAT问题类的严格相变仍然是突出问题．随机均衡正则恰当(2s，k)-SAT问题为正则k-SAT问题的一类特殊子问题，分析该问题的相变须引入该问题的随机实例产生模型，主要思想是将二部图中的节点分为两类，利用两类节点之间的随机匹配产生二部图．即将每个变元的正负文字分别复制s次形成2sn个变元节点，在变元节点和子句节点之间随机形成一个完美匹配，每一个匹配对应一个随机均衡正则(2s，k)-SAT实例．本研究针对均衡正则恰当(2s，k)-SAT问题的相变展开研究，引入随机均衡正则(2s，k)-SAT实例产生模型，利用一阶矩方法和二阶矩方法，给出该问题的相变点．选择变元规模为n=10的随机均衡正则恰当(2s，k)-SAT实例进行实验，验证了k=4和k=6两种情形，理论结果与实验结果符合．1 均衡正则(2s，k)-SAT实例模型布尔变元的集合V={x1,x2,⋯,xn}，每个变元xi(1≤i≤n)有正文字xi和负文字¬xi两种形态．子句Ci由文字L的析取构成，Ci=L1∨L2∨ ⋯∨Lk，其中k为子句的长度，Var(Cr)为Cr(1≤r≤m)中变元的集合，其中m为子句的个数．命题公式(CNF公式)F是由子句的合取构成，F=C1∧C2∧⋯∧Cm，Var(F)为F中变元的集合．一个均衡正则(2s，k)-CNF公式是指：在CNF公式F中，每个变元恰好出现2s次，并且正负出现的次数相等，均为s次，每个子句的长度恰好为k．均衡正则恰当(2s，k)-SAT问题是指：是否存在一个真值指派τ={a1,a2,⋯,an}，使得(2s，k)-CNF公式中的每个子句Cj恰有一个文字取真值．设变元集V={x1,x2,⋯,xn}，将V中的每个变元复制2s个，做如下变元矩阵V*=x1,1x1,2⋯x1,2sx2,1x2,2x2,2s⋮⋱⋮xn,1xn,2⋯xn,2s，式中xn,2s为一个布尔命题变元．设子句集C={C1,C2,⋯,Cm}，将C写为C*=L1,1L1,2⋯L1,kL2,1L2,2L2,k⋮⋱⋮Lm,1Lm,2⋯Lm,k，式中Lm,k为一个文字．注意：km=2sn．通过以下步骤，构造一个随机均衡正则(2s，k)-SAT实例．a. 生成无符号公式：集合S={1,2,⋯,km}上所有置换构成样本空间，共有(km)!个置换，从中随机取一个置换构成一个无符号公式．b. 实现符号矩阵R：对每个行号i，在集合[2s]={1,2,⋯,2s}中选取一个s元子集，将[2s]划分为两部分，这样的划分共有C2ss=(2s)!/(s!)2．对每个划分分别赋予正(+)、负(-)号，配上正、负号后，形成不同的符号行，这样的配有符号的行共有2(2s)!/(s!)2≈22s+1/πs．按集合指示的列标，形成一个准确的位置符号行Ri．以Ri作为符号矩阵R的第i行，形成一个n×(2s)的符号矩阵，这样的符号矩阵共有(22s+1/πs)n=(1/πs)n2(2s+1)n．将R作用在V*上，称为一个实现．即给V*中对应位置的变元赋以符号，记为R(V*)，R(V*)是一个文字矩阵．c. 生成均衡正则(2s，k)-SAT实例：随机取一个置换μ和R，将μ作为R(V*)到C*的一对一映射，对应生成一个均衡正则(2s，k)-SAT实例．根据上述步骤，产生的均衡正则(2s，k)-SAT实例的个数为(km)![2(2s)!/(s!)2]n=(2sn)![2(2s)!/(s!)2]n．2 均衡正则(2s，k)-SAT相变分析均衡正则恰当(2s，k)-SAT问题是NP难问题，对该问题的可满足性相变研究，是设计求解该问题有效算法的重要依据．利用一阶矩方法和二阶矩方法给出随机均衡正则恰当(2s，k)-SAT问题的可满足相变点．定理1 F是一个随机均衡正则恰当(2s，k)-SAT问题实例，设s*=k4(k-1)(ln k-ln(k-1))．当k≥3时，对于任意的整数s，有limn→∞Pr[F可满足]=1    (ss*);0    (ss*).定理1表明：设k≥3，对于一个随机均衡正则恰当(2s，k)-SAT问题实例F，若ss*，则F高概率可满足；若ss*，则F高概率不可满足．为了证明定理1须要证明如下两个引理．引理1 设k≥3，当ss*时，F高概率不可满足．引理2 设k≥3，当ss*时，F高概率可满足．首先证明引理1，设V={x1,x2,⋯,xn}上的一个真值指派v={v1,v2,⋯,vn}，其中vi∈{0,1}．T={l1,l2,⋯,ln}是v对应的取值为真的文字的集合，若v(xi)=1，则li=xi；若v(xi)=0，则li=¬xi．F=C1∧C2∧⋯∧Cm是一个均衡正则(2s，k)-SAT实例，均衡正则恰当(2s，k)-SAT可满足问题是指：是否存在一个T，使得对于F中的每一个子句Cj，满足|T⋂Cj|=1．构造包含T中元素的一个实现R(V*)，用T中的元素对应置换C*中每行上的一个元素，每个元素最多置换C*中的s行，并且T中所有元素置换的行数总和不能超过m．由于每一行上有k个位置(注意：km=2sn)，因此这样的置换共有m!km种可能．通过置换后，每一行还有k-1个空位置，这些空位置由R(V*)中剔除T中的元素补充，这样的置换共有(m(k-1))!种可能，而包含T的实现R(V*)有(2C2s-1s-1)n，因此T所满足的公式数共有(2C2s-1s-1)nm!km(m(k-1))!．实例空间中共有可满足公式的个数为2n(2C2s-1s-1)nm!km(m(k-1))!．假定随机均匀的从实例空间中取一个实例F，若以随机变量Z(n)表示F的解的个数，则Z(n)的数学期望为E[Z(n)]=2n(2C2s-1s-1)nm!km(m(k-1))!(km)![2(2s)!/(s!)2]n=2n(C2s-1s-1)nm!km(m(k-1))!(km)![(2s)!/(s!)2]n.根据马尔科夫不等式及一阶矩，接下来须证明limn→∞E[Z(n)]=0．E[Z(n)]=2n(C2s-1s-1)nm!km(m(k-1))!(km)![(2s)!/(s!)2]n=m!km(m(k-1))!(km)!=kmCkmm=km2πm1-1k∙exp[-kmH1k]=2π1-1k2sk∙exp[-2snH1k+2snklnk+12ln n]≤2π1-1k2skexp[-2snH1k+2snkln k+12n]=2π1-1k2sk∙exp[n(-2sH1k+2skln k+12)].设函数ρ(s)=-2sH1k+2skln k+12，其中H1k为熵函数，H1k=-1kln 1k-1-1kln1-1k，因此ρ(s)=-2sH1k+2sklnk+12=-2s∙-1kln 1k-1-1kln1-1k+2sklnk+12=2s1-1kln1-1k+12. (1)可以验证，当k≥3时，函数ρ(s)是关于s的单调下降函数(见图1)，且有一个零点s*，s*=14k(k-1)1lnk-ln(k-1).10.13245/j.hust.220216.F001图1函数ρ(s)的图像(k=4)当k≥3且ss*时，limn→∞E[Z(n)]=0，因此有Prn→∞[Z(n)≥1]=0．即当k≥3且ss*时，随机均衡正则恰当(2s，k)-SAT实例高概率不可满足，引理1证毕．注意：当k=3时，s*=0.924 9，因此重点考虑k≥4的情况．下面证明引理2，主要是计算E[Z2(n)]的值．假定F是一个可满足的实例，设有t个满足指派的集合{T1,T2,⋯,Tt}．称一对指派(Ti,Tj)满足F，当且仅当Ti和Tj同时满足F．考虑{T1,T2,⋯,Tt}上的指派对集合{(Ti,Tj):1≤i,j≤t}，指派对的个数为t2，不妨设Tij=(Ti,Tj)，指派对可以表示为T*=T11T12⋯T1tT21T22T2t⋮⋱⋮Tt1Tt2⋯Ttt．注意到，对于公式F，任意一个满足指派T的大小为n．从而，对于任意一个指派对(Ti,Tj)，有：|Ti-Tj|=|Tj-Ti|;0≤|Ti⋂Tj|≤n,0≤|Ti-Tj|≤n.利用集合差的大小对集合{(Ti,Tj)|1≤i,j≤t}进行划分，分为n+1类．当|Ti-Tj|=|Tl-Th|=λ时，(Ti,Tj)和(Tl,Th)在同一个类中，记为Pλ={(Ti,Tj):|Ti-Tj|=λ}．可见P0,P1,⋯,Pn形成对{(Ti,Tj)|1≤i,j≤t}的一个划分，并且有|P0|+|P1|+⋯+|Pn|=t2．在一个划分块Pλ中，|Ti-Tj|=|Tj-Ti|=λ，|Ti⋂Tj|=n-λ，共涉及到的文字为n+λ个，还有n-λ个文字不在指派对(Ti,Tj)中．引入一个归一化参数ω (0≤ω≤1)，将求和表现为积分．对划分做标记Qω=Pωn={(Ti,Tj):|Ti-Tj|=ωn}．Qω块中的集合对(Ti,Tj)满足：|Ti-Tj|=|Tj-Ti|=ωn;|Ti⋂Tj|=(1-ω)n;|Ti⋃Tj|=(1+ω)n.以一组满足指派对为例，计算被满足公式的数目．设：Ti={l1,l2,⋯,lωn,lωn+1,⋯,ln}；Tj={lωn+1,lωn+2,⋯,ln,ln+1,⋯,l(1+ω)n}．对于公式F中的每一个子句C，由|Ti⋂C|=1可知Ti中的每一个文字对应分配到F中的若干子句中，因此每一个文字分配到F中子句的期望数为m/n．根据满足指派与子句位置的匹配关系，有如下三种情况．a. 由Ti和Tj满足公式及|Ti⋂Tj|=(1-ω)n可知这部分文字满足的期望子句数为(1-ω)m．由于Ti和Tj中的这部分文字相同，因此在对应置换矩阵中，匹配方式的数量为((1-ω)m)!k(1-ω)m．b. 由Ti和Tj满足公式及|Ti-Tj|=|Tj-Ti|=ωn可知，这部分文字满足的期望子句数为ωm．由于Ti和Tj中的这部分文字不同，因此在对应置换矩阵中，匹配方式的数量为(ωm)!kωm∙ (ωm)!k-1ωm．c. 通过a和b匹配后，剩余未被匹配的空位置数量为(1-ω)m(k-1)+ωm(k-2)=m(k-1-ω)．这部分匹配共有(m(k-1-ω))!.包含Ti的实现为RTi(V*)，包含Tj的实现为RTj(V*)．这些空位置由RTi(V*)和RTj(V*)中不包含Ti和Tj的元素补充．由于|Ti⋂Tj|=(1-ω)n，因此(Ti,Tj)的实现RTi⋂Tj(V*)共有(C2s-1s-1)(1-ω)n．对于|Ti-Tj|=|Tj-Ti|=ωn的情况，根据正、负文字出现均等的约束条件，(Ti,Tj)的实现RTi-Tj(V*)共有2(C2s-1s-1)ωn，因此对于给定的Ti和Tj，(Ti,Tj)共满足的公式数为Cmωm2(C2s-1s-1)ωn(C2s-1s-1)(1-ω)n[(1-ω)m]!∙k(1-ω)m(ωm)!kωm(ωm)!k-1ωm[m(k-1-ω)]!=2Cmωm(C2s-1s-1)n[(1-ω)m]!k(1-ω)m∙(ωm)!kωm(ωm)!k-1ωm[m(k-1-ω)]!=2(C2s-1s-1)nkm(k-1)ωmm!(ωm)![m(k-1-ω)]!.Qω中的指派对满足的公式数为2|Qω|(C2s-1s-1)n∙ kmk-1ωmm!(ωm)!(m(k-1-ω))!.指定一个大小为n的集合T，设T'与T满足|T' |=n,|T-T'|=|T'-T|=ωn，这样的T'共有(2ωn-1)Cn(1-ω)n=(2ωn-1)Cnωn，因此Qω的大小为2(1-ω)n(2ωn-1)Cnωn≈2nCnωn．Qω中的所有指派对满足的公式数为2n+1Cnωn∙ (C2s-1s-1)nkmk-1ωmm!(ωm)!(m(k-1-ω))!.设Zω(n)为随机抽到公式被Qω中指派对满足的计数随机变量，则      E[Zω(n)]=[2n+1Cnωn(C2s-1s-1)nkmk-1ωmm!∙(ωm)!(m(k-1-ω))!]/[(km)!(2C2ss)n]=21-nk-1ωmE[Z(n)][Cnωn/Cm(k-1)ωm].将组合近似公式Cnαn≈[2πnα(1-α)]-1/2enH(α) (0α1)化简，即    CnωnCm(k-1)ωm=2πm(k-1)[ω/(k-1)][1-ω/(k-1)]2πnω(1-ω)∙exp[nH(ω)-m(k-1)H(ω/(k-1))]=2s[1-ω/(k-1)]k(1-ω)exp[nH(ω)-m(k-1)∙H(ω/(k-1))],因此有E[Zω(n)]=21-nk-1ωmE[Z(n)]2s[1-ω/(k-1)]k(1-ω)∙exp[nH(ω)-m(k-1)H(ω/(k-1))]=E[Z(n)]2s[1-ω/(k-1)]k(1-ω)exp[nH(ω)-m(k-1)H(ω/(k-1))]+ωmln(k-1)+(1-n)ln 2].又因为E[Z2(n)]=∑j=0nE[Zj/n(n)]=E[Z(n)]+∑j=1nE[Zj/n(n)],用ωj替代j/n，有      E[Z2(n)]=E[Z(n)]+∑j=1nE[Zωj(n)]=E[Z(n)]{1+∑j=1n2s[1-ωj/(k-1)]k(1-ωj)∙exp[nH(ωj)-m(k-1)H(ωjk-1)+ωjmln(k-1)+(1-n)ln 2]}≈E[Z(n)]∙{1+∑j=1n2s[1-ωj/(k-1)]k(1-ωj)exp[n(H(ωj)-2sk(k-1)H(ωjk-1)+2sωjkln(k-1)-ln 2)]}.设函数ψ(ωj)=H(ωj)-2sk(k-1)H(ωjk-1)+2sωjkln(k-1)-ln 2;f(ωj)=2s[1-ωj/(k-1)]k(1-ωj)，则E[Z2(n)]=E[Z(n)](1+∑j=1nf(ωj)enψ(ωj))=E[Z(n)]2(βe-nφ(s)+βe-nφ(s)∑j=1nf(ωj)enψ(ωj)),式中β=[2π(1-1/k)(2s/k)]-1/2．将累加和转换为积分，有E[Z2(n)]≈E[Z(n)]2(βe-nφ(s)+βe-nφ(s)n∫01f(ω)enψ(ω)dω),式中ψ(ω)=H(ω)-2sk(k-1)Hωk-1+2sωkln(k-1)-ln 2=-ωln ω-(1-ω)ln(1-ω)+2skωln ω+2sk∙(k-1-ω)ln1-ωk-1-ln 2.由前文可知：H'(ω)=[-ωlnω-(1-ω)ln(1-ω)]'=ln(1-ω)-lnω;H'ωk-1=-ωk-1lnωk-1-1-ωk-1∙ln1-ωk-1=1k-1ln1-ωk-1-1k-1lnωk-1.因此有：ψ'(ω)=ln(1-ω)-lnω-2sk∙ln1-ωk-1-lnωk-1+2sk∙ln(k-1)=ln(1-ω)-lnω+2sklnω-2skln1-ωk-1;ψ″(ω)=2sk-11ω+2sk(k-1-ω)-11-ω．当k=4时，根据式(1)得到s*=1.158 7，当k=6时，根据式(1)得到s*=1.645 4，函数ψ(ω)的图像如图2所示．10.13245/j.hust.220216.F002图2函数ψ(ω)的图像可以验证，当k≥3且ss*时，ψ″(ω)0，ψ(ω)在(0,1)区间内光滑，且有唯一最大值点．不妨设ωmax是ψ(ω)的最大值点，依据文献[7]得limn→∞∫01f(ω)enψ(ω)dω≈f(ωmax)2πn|ψ″(ωmax)|enψ(ωmax),因此，E[Z2(n)]≈E[Z(n)]2{βe-nρ(s)+f1(ωmax)∙(n/n)exp[n(ψ(ωmax)-ρ(s))]}=E[Z(n)]2∙{βe-nρ(s)+f1(ωmax)n1/2exp[n(ψ(ωmax)-ρ(s))]},式中f1(ωmax)=12sk1-1k1|ψ″(ωmax)|f(ωmax)．设φ(s)=ψ(ωmax)-ρ(s)，当0ω1时，取k=4和k=6，函数φ(s)的图像如图3所示．10.13245/j.hust.220216.F003图3函数φ(s)的图像可以验证：当k≥3且ss*时，φ(s)在区间(0，1)内光滑非正，且有唯一最大值点，因此E[Z2(n)]≈E[Z(n)]2{βe-nφ(s)+f1(ωmax)∙[n/exp(n|ψ(ωmax)-φ(s)|)]},当ss*，n→∞时，E[Z2(n)]=E[Z(n)]2(1+o(1))．综上所述，Prn→∞[Z(n)=0]=0，Prn→∞[Z(n)0]=1．即，当ss*时，随机均衡正则恰当(2s，k)-SAT实例高概率可满足．引理2证毕．由引理1和引理2可知：当ss*时，随机均衡正则恰当(2s，k)-SAT实例高概率可满足；当ss*时，随机均衡正则恰当(2s，k)-SAT实例高概率不可满足．定理1证毕．3 数值实验及分析在实验中，取n=10，利用随机均衡正则恰当(2s，k)-SAT实例模型生产随机实例．根据定理1，当k=4时，s*=1.158 7；当k=6时，s*=1.645 4．图4为随机均衡正则恰当(2s，k)-SAT问题的相变，图中每个数据点均由100个随机实例的统计结果产生，s为定理1中的相变控制参数，Pr为随机均衡正则恰当(2s，k)-SAT实例可满足的统计概率．10.13245/j.hust.220216.F004图4随机均衡正则恰当(2s，k)-SAT问题的相变(n=10)在实验设计中，由于对s和m做了四舍五入的调整，因此产生了较小误差．但随着问题规模的增加，这种四舍五入带来的误差对相变的影响逐步减弱．理论上讲，随着问题规模的进一步增大，实验结果会越来越精确．图4表明实验结果与理论结果符合．同时，对于随机均衡正则恰当(2s，k)-SAT实例的求解算法，实验中采用赋值验证的方法，通过穷举所有赋值(共有2n个赋值)，验证公式是否能够恰当可满足，因此问题规模设置较大，增加了算法求解的时间复杂程度．4 结语分析了随机均衡正则恰当(2s，k)-SAT问题的可满足性相变点，给出了该问题关于s的相变点．设s*是关于k(k2)的一个常数，F是一个随机均衡正则恰当(2s，k)-SAT问题实例．对于整数s，若ss*，则F是高概率可满足的；若ss*，则F是高概率不可满足的．均衡正则恰当(2s，k)-SAT问题可以看作是正则(d，k)-SAT问题的一种特殊情况，对该问题相变现象的分析，有助于分析正则(d，k)-SAT问题及其同类型问题的相变．