k-LSAT(k≥3)是NP-完全的(英文)

合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关.即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.     

极小不可满足公式在多项式归约中的应用

合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式限制于(r,s)-CNF.对于正整数r≥3,有一个临界函数f(r),使得(r,f(r))-CNF中的公式都是可满足的,而(r,f(r)+1)-SAT却是NP-完全的.函数f是否可计算是一个开问题,除了知道f(3)=3,f(4)=4外,只能估计f(r)的界.描述了极小不可满足公式在CNF公式类之间转换中的作用.为使转换过程中引入较少的新变元,给出了CNF公式到3-CNF公式的一种新的转换方法,对于长度为l(＞3)的子句,仅需引入|l/2|个新变元.并且,给出了CNF到(r,s)-CNF公式转换以及(r,s)-CNF中不可满足公式构造的原理和方法.     

不可满足公式的同态证明系统

合取范式(CNF)公式H到F的同态φ是一个从H的文字集合到F的文字集合的映射,并保持补运算和子句映到子句.同态映射保持一个公式的不可满足性.一个公式是极小不可满足的是指该公式本身不可满足,而且从中删去任意一个子句后得到的公式可满足.MU(1)是子句数与变元数的差等于1的极小不可满足公式类.一个三元组(H,φ,F)称为的一个来自H的同态证明,如果φ是一个从H到F的同态.利用基础矩阵的方法证明了:一个不可满足公式F的树消解证明,可以在多项式时间内转换成一个来自MU(1)中公式的同态证明.从而,由MU(1)中的公式构成的同态证明系统是完备的,并且由MU(1)中的公式构成的同态证明系统与树消解证明系统之间是多项式等价的.     

MAX(1)和MARG(1)中公式改名的复杂性

改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题"对于给定的CNF公式H和F是否存在一个变元(或文字)改名ψ使得ψ(H)=F?"的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

一个正则NP-完全问题及其不可近似性

通过一个适当的归约变换,可以将一个CNF (conjunctive normal form)公式变换为另一个具有某种特殊结构或性质的公式,使两者具有相同的可满足性.带有正则结构的CNF公式的因子图在图论中具有某些良好的性质和结果,可以用于研究公式的可满足性和计算复杂性.极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足.借助此临界特性,给出了一个从3-CNF公式到正则(3,4)-CNF公式的多项式归约转换.这里,正则(3,4)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4.因此,正则(3,4)-SAT问题是一个NP-完全问题,并且MAX(3,4)-SAT是不可近似问题.     

k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

命题线性时序逻辑的对偶模型问题的复杂性

定义了一个命题线性时序逻辑的对偶模型的概念.一个公式f的对偶模型是指f的满足以下条件的两个模型(即状态的w序列):在每个位置上这两个模型对原子命题的赋值都是对偶的.然后,对于确定一个公式f是否有对偶模型的判定问题(记为DM)和在一个Kripke-结构中确定是否存在从两个给定状态出发的对偶模型满足给定公式f的判定问题(记为KDM)的复杂性进行了研究.证明了以下结果:对于只含有F("Future")算子的命题线性时序逻辑,DM和KDM都是NP完全的;而对于以下命题线性时序逻辑,DM和KDM都是PSPACE完全的:含有F,X ("Next")算子的逻辑、含有U("Until")算子的逻辑、含有U,S,X算子的逻辑以及由Wolper给出的含有正规语言算子的逻辑(一般称为扩展时序逻辑,简称ETL).     

结合可信度的km-means算法

以K-means为代表的聚类算法被广泛地应用在许多领域, 但是K-means不能直接处理不完整数据集. k_m-means是一种处理不完整数据集的聚类算法, 通过调整局部距离计算方式, 减少不完整数据对聚类过程的影响. 然而k_m-means初始化阶段选取的聚类中心存在较大的不可靠性, 容易陷入局部最优解. 针对此问题, 本文引入可信度, 提出了结合可信度的k_m-means聚类算法, 通过可信度调整距离计算, 增大初始化过程中选取聚类中心的可靠性, 提高聚类算法的准确度. 最后, 通过UCI和UCR数据集验证算法的有效性.     

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

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则（k,2s）-CNF公式.受严格正则（k,2s）-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k,2s）-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机（k,2s）-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机（3,2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机（3,2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机（3,2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

资源独立工作流可满足性的最小增量模式回溯

工作流可满足性是业务安全规划的基本问题, 正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战. 在资源独立约束下, 其最高效求解途径是模式空间上的增量回溯法IPB. 为克服结点真实性验证的性能瓶颈, 它增量计算模式k指派(二部)图及其(左完备)匹配, 分别需要O(kn)和O(k²)时间. 利用父子模式的原子差异增量计算完全指派图, 只需O(n)时间, 特别是其实际性能, 将随模式块规模增长迅速提高. 但该图的O(kn)规模导致了同样的增量匹配时间. 进而引入完备k核心匹配概念, 证明其存在性等价于左完备匹配, 且其增量计算时间为O(k²). 由此, 建立了时间复杂度更低的最小增量模式回溯法. 在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验, 结果表明: 当n/k=10(及n/k=100), 而k变化时, 该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势; 当k=18(及k=36), 而n/k=2~4096(及n/k=2~2048)时, 该方法有平均超过2.6(及3.6)倍优势; 而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT, 该方法最低有超过3倍优势.     

Goguen命题逻辑系统公理化扩张的Γ-k真度理论及性质

本文首先对n值Goguen命题逻辑进行公理化扩张,Goguen_~,△,记为Π_~,△.利用公式的诱导函数给出公式在k（k任取~或△）连接词下相对于局部有限理论Γ的Γ-k真度的定义;讨论了Π_~,△中Γ-k真度的MP规则、HS规则等相关性质;最后,在Π_~,△中定义了两公式间的Γ-k相似度与Γ-k伪距离,得到了公式在连接词下相对于局部有限理论Γ的Γ-k相似度与Γ-k伪距离所具有的一些良好性质.     

RB模型实例集上置信传播算法的收敛性

置信传播算法求解RB（k,n,α,r_c,p）模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB（k,n,α,r_c,p）模型中,取k=2,α>（1/k）,r_c>0均为常数,且满足ke^{-（α/（r_c））}≥1.证明了如果p∈（0,n^-2α）,则置信传播算法在RB（k,n,α,r_c,p）模型产生的随机实例集上高概率收敛.最后,在RB（k,n,α,r_c,p）模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RB（k,n,α,r_c,p）模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RB（k,n,α,r_c,p）模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关.     

P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

Fq上具有极大1-error线性复杂度的周期序列

线性复杂度是衡量序列密码学强度的重要指标,设计具有大的线性复杂度和k-error线性复杂度的序列是密码学和通信中的热点问题.Niederreiter首次发现了F_q上许多满足这个要求的周期序列.通过序列的广义离散傅立叶变换构造了一些F_q上具有极大1-error线性复杂度的周期序列,这些结果远远优于已知的结果.     

基于聚类和划分的SAT分治判定

提出了一种将布尔公式划分为子句组来进行布尔可满足性判定的方法.CNF(conjunctive normal form)公式是可满足的当且仅当划分产生的每个子句组都是可满足的,因此,通过判定子句组的可满足性来判定原公式的可满足性,相当于用分治法将复杂问题分解为多个子问题来求解.这种分治判定方法一方面降低了原公式的可满足性判定复杂度;另一方面,由于子句组的判定可以并行,因而判定速度能够得到进一步的提高.对于不能直接产生布尔子句组划分的情形,提出了一种利用聚类技术将CNF公式聚类成多个簇,然后消去簇间的公共变量来产生子句组划分的方法.     

MAX(1)和MARG(1)中公式改名的复杂性

改名是一个将变元映射到变元本身或它的补的函数,变元改名是公式变元集合上的一个置换,文字改名是一个改名和一个变元改名的组合.研究CNF公式的改名有助于改进DPLL算法.考虑判定问题"对于给定的CNF公式H和F是否存在一个变元(或文字)改名ψ使得ψ(H)=F?"的计算复杂性.MAX(1)和MARG(1)是极小不可满足公式的两个子类,这两个子类中的公式可以用树表示.树同构的判定问题在线性时间内是可解的.证明了对于MAX(1)和MARG(1)中的公式,文字改名问题在线性时间内可解,变元改名问题在平方次时间内可解.     

完全析取范式群判定SHOIN(D)-可满足性

针对非循环概念提出了一种对SHOIN(D)-概念可满足性进行判断的方法——CDNF(complete disjunctive normal form)算法.该算法通过把非循环定义的概念描述本身构建成分层次的析取范式群,并通过子句重用技术阻止无谓的子概念扩展,这样的析取范式群具有可满足性自明性,从而可以实现对SHOIN(D)-概念可满足性的直接判断.该算法基本上消除了判断过程中描述重复的现象,从而在空间、时间性能上都比Tableau算法有更好的表现.