均衡正则恰当(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问题及其同类型问题的相变.

使用Chrome浏览器效果最佳,继续浏览,你可能不会看到最佳的展示效果,

确定继续浏览么?

复制成功,请在其他浏览器进行阅读