可满足性问题的研究综述

对SAT问题及其各种约束子问题进行分类并给出具体定义,着重介绍常规SAT问题、最大可满足性问题（MAX—SAT）和参数化SAT问题的相关算法,并对参数算法中运用的技术进行分析和比较,提出一些SAT问题研究中值得关注的几个方面。     

一类可分离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—完全问题在阈图上的解

本文给出了判定阈图是否为哈密顿图的多项式时间算法,并证明了阈图上STEINER树问题是NP-完全的,给出解答它的多项式时间近似算法。     

MSP问题NP完全性研究

针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。     

特殊形式和结构的MSP问题NP完全性研究

针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化.以简化证明为导引,提出一种特殊形式和结构的MSP问题.而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义.因此,提出的特殊形式和结构的MSP问题进行了NP完全性质证明.类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并进一步推动原问题的研究.     

浅谈NP问题

NP完全问题在科学研究和实际应用中广泛存在,仅仅指出它们的难解性是不够的,更重要的是正面寻求解决方法,其中的关键是算法的设计与分析。     

一种三值逻辑的NP完全问题与判定问题

本文建立了一种三值逻辑——中介逻辑的三值语义,证明了其命题演算MP与MP的可满足问题是NP完全的且其谓词演算(带或不带等词)MF,MF与ME的判定问题是算法不可解的。     

DNA自组装的可满足性问题模型

DNA自组装技术在DNA计算和纳米技术领域都发挥着极其重要的作用,许多小规模NP完全问题都可以通过自组装模型得以解决.文中以可满足问题为模型,通过构造范式中变量的特殊补链,使其与初始数据库中初始DNA链发生杂交反应,形成发夹结构,利用形成发夹结构的DNA链与没形成发夹结构的DNA链长度不同的特点,通过凝胶电泳将这些带发夹的DNA链提取出来;然后加入与这些特殊补链完全互补的DNA链,在一定温度下,通过碱基互补配对原则,发夹结构又将被重新打开.该模型充分利用了DNA分子间的自组装能力,在计算过程中只需要用到凝胶电泳操作,在一定程度上大大减少了因生物操作过多而引起的各种实验误差.     

非线性存储方案设计问题--一个NP完全问题

本文证明了为任意模板集设计存储访问无冲突非线性存储的总理２理一个ＮＰ完全总理２,另外设计同时满足存储访问中突和互联网络无冲突和互联先冲突的存储方案设计问题也是一个ＮＰ完全问题。     

解Job－shop调度问题的神经网络方法

研究用神经网络方法解决Ｊｏｂ－ｓｈｏｐ调度问题．首先描述解Ｊｏｂ－ｓｈｏｐ调度问题的算法，然后给出这一算法及其网络性质的理论结果．仿真实验结果证明了该方法是可行的．最后，针对几类典型调度问题的解决进一步说明了这一方法的优势．     

关于约束底盘装载问题的一种启发式方法

已研究多年的底盘装载问题属于ＮＰ完备问题，关于它的解决方法多为启发式方法．本文讨论了约束底盘装载问题，并提出了一种基于计算机的启发式方法．实例表明，该方法能较好地解决约束底盘装载问题．     

遗传算法求解完全欺骗性问题的平均计算时间

讨论了一类遗传算法求解完全欺骗性问题的平均计算时间,证明了这类算法的平均计算时间是问题规模的指数次方,同时指出存在一种基于多重结构的遗传算法,它求解这个问题的２计算时间是问题规模的多项式次方。     

货郎担问题的几何解法

本文提出货郎担问题的一种新的求解方法，即几何解法．它的时间复杂性为：求距离运算次数为Ｏ（ｎｍ），比较次数为Ｏ（ｍａｘ（ｎｍ，ｎｌｏｇｎ）），求夹角次数为Ｏ（n²/m），其中ｎ为点集中点的数目，ｍ为点集的凸包顶点数．     

解Job-shop调度问题的混合模拟退火进化规划

提出运用混合模拟退火进化规划（ＳＡＥＰ）求解Ｊｏｂ－ｓｈｏｐ调度问题．首先介绍了ＳＡＥＰ和进化规划（ＥＰ）的不同选择方法以及他们的变异算子,最后给出了仿真实例,并比较了这两种算法的优劣     

Linear kernelizations for restricted 3-Hitting Set problems

In this paper, we study the 3-Hitting Set problem, also called the Vertex Cover problem on 3-uniform hypergraphs. We provide linear kernelizations for this problem and its dual problem in three types of 3-uniform hypergraphs. Moreover, we obtain lower bounds on the kernel size for them by the parametric duality technique.     

一类异步多速率采样控制系统的近似问题

本文提出了一类异步多速率采样控制系统．针对这类非周期异步多速率系统分析、设 计困难这一问题，研究了其闭环系统性能关于采样器、保持器时间延迟的连续性问题．结果 表明，其闭环系统性能是采样器、保持器时间延迟的连续函数．据此连续性，在少许改变系 统性能的前提下，可以以任意给定精度将非周期异步多速率系统转变成周期异步多速率系统 ，再应用已有方法对其进行处理．     

基于一类特殊问题的排序算法

本文提出了一类特殊问题的拓序算法，其特点是在内排序中关键字与数组下标作映射或链接处理，不实施反复比较与交换关键字的操作，时间复杂性达到O（N）；在外排序中，文件输入／输出次数减少，提高了效率 。这类算法适宜今后在相关大规模信息处理中广泛应用。     

A note on the complexity of matching patterns with variables

A word matches a pattern with variables (i.e., a string that contains terminal symbols and variable symbols) if and only if it can be obtained from the pattern by substituting the variables by terminal words. To decide for a given word whether or not it matches a pattern with variables is an NP-complete problem, which has been independently discovered and investigated in different areas of theoretical computer science and which has applications in various contexts. In this work, we show that the problem of matching patterns with variables remains NP-complete even if every variable has at most two occurrences. In addition to this, we show that if patterns can be represented as special kinds of planar graphs, then they can be matched in polynomial time.