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-完全的.

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

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

直径为5的图的2-导出匹配划分和2-导出匹配覆盖问题的NP-完全性(英文)

给定一个简单图G和正整数k,具有完美匹配的图G的k-导出匹配划分是对顶点集V(G)的一个k-划分(V_1,V_2,…,V_k),其中对每一个i(1≤i≤k),由V_i导出的G的子图G[V_i]是1-正则的.k-导出匹配划分问题是指对给定的图G,判定G是否存在一个k-导出匹配划分.令M_1,M_2,…,M_k为图G的k个导出匹配,如果V(M_1)∪V(M_2)∪…∪V(M_k)=V(G),则我们称{M_1,M_2…,M_k}是G的k-导出匹配覆盖. k-导出匹配覆盖问题是指对给定的图G,判定G是否存在k-导出匹配覆盖.本文给出了Yang,Yuan和Dong所提出问题的解,证明了直径为5的图的导出匹配2-划分问题和导出匹配2-覆盖问题都是NP-完全的.

DNA计算原理在NP-完全问题中的应用

DNA计算是一种利用生物分子间的相互作用来实现并行计算的新的计算模式,具有高度的并行性、巨大的信息存储能力和极低的能耗等优点。该文对DNA计算的一般原理进行了介绍,且介绍了DNA计算原理在解决NP问题方面所取得的进展,并指出了DNA计算中存在的问题。

一类NP-完全问题在阈图上的解

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

两类广义控制问题的NP-完全性(英文)

研究两类广义控制问题的复杂性:κ-步长控制问题和κ-距离控制问题,证明了κ-步长控制问题在弦图和平面二部图上都是NP-完全的,作为上述结果的推论,给出了κ-距离控制问题在弦图和二部图上NP-完全性的新的证明,并进一步证明了κ-距离控制问题在平面二部图上也是NP-完全的。

偶图的补图的侧廓问题和填充问题的NP-完全性(英文)

本文研究偶补图的侧廓问题和填充问题的计算复杂性，证明了：即使对直径不超过2的偶补图，侧廓问题和填充问题也是NP－完全的．

生物信息学中的NP-完全问题研究综述

介绍几个生物信息学中的NP-完全问题以及目前文献对这些问题的解决方法,分析目前解决NP-完全问题的计算智能算法及存在的问题,总结计算智能方法在生物信息学领域的研究热点以及未来研究应该注意的问题。

DNA计算在求解NP-完全问题的应用

基于生化反应的DNA计算模型越来越受到关注。DNA计算的研究已经成为一个热点。本文主要介绍了DNA计算在一些NP-完全问题中的应用。并分析了DNA模型存在的问题。指出未来国内DNA计算研究的重点可以在三个方面:解的检测,降低空间复杂度,生化实验研究。

3-正则图的分割问题是NP-完全问题

证明了3-正则图的最小平分问题和最小α-分割问题都是NP-完全问题.

遗传算法用于NP完全问题的求解

讨论了如何利用遗传算法求解布尔表达式的可满足性问题 ,并给出该结果对求解其他NP完全问题时的应用 .

图的路色数问题的NP－完全性

一个给定的图是否存在用ｒ种颜色的正常Ｐｋ着色？称该问题为图的（ｋ，ｒ）路色数问题．本文研究其算法复杂性，并得到以下结果：对于任意给定的ｋ，２≤ｋ≤∞，图的（ｋ，２）路色数问题及直径为２的图的（ｋ，３）路色数问题都是ＮＰ－完全的；对于任意给定的ｋ，２≤ｋ≤∞，平面图的（ｋ，３）路色数问题也是ＮＰ－完全的．

一些简化的NP完全实例类(英文)

(k,s)-SAT是命题满足性问题限制在一种特殊的命题公式上, 该命题公式具有每个子句只有k个不同的文字且每个变元出现的次数少于s次的特点。已经验明对于正整数k,s存在一个指数函数f, 满足:对任意s≤f(k), 所有的(k,s)-SAT例都是可满足的, 而(k,f(k)+1)-SAT却是一个NP-完全问题。目前为止, 只知道f(3)和f(4)的精确值.对于f是否可计算是一个仍未解决的问题.由于每个满足某种条件的数值序列对应一个MU(1)中的公式, 在[2]中,作者S. Horry和S. Seizder通过对数值序列的运算来构造(k,s)-SAT中的MU(1)公式例, 得到了函数f的可计算上界函数。但当k比较大时, 该方法不太实用。作者定义了一种树规则来减少数值计算的步数, 得到了一个确定的实用的算法来计算函数f的上界, 该上界接近[2]中的上界,同时,也得到了一些NP-完全满足性问题类。

基于角色访问控制管理模型的安全性分析

在基于角色的访问控制管理模型中,采用安全查询来描述系统安全策略,引入状态变换系统定义基于角色的访问控制管理模型及其安全分析,用图灵机理论和计算复杂性理论进行安全分析.将安全查询分类为必然性安全查询和可能性安全查询,证明了必然性安全查询和与状态无关的可能性安全查询能在多项式时间内被有效解决,给出了满足NP-完全问题的可能性安全查询的条件,而一般的可能性安全查询是不可判定的.

布局问题的模拟退火算法

布局问题属于ＮＰ－完全问题已被研究多年．模拟退火法是一种新的通用启发式优化算法，现已广泛用于解决大规模集成电路逻辑布线设计、图象处理等组合优化问题．本文通过对布局问题及模拟退火算法的分析，将它们综合起来构成了求解布局问题的模拟退火算法．计算结果表明，本文算法得到的解优于传统优化方法所得到的解；文章还通过实验对算法中各参数所起作用进行了论述．

旋转锥体空间中圆柱体群的布局优化

旋转圆锥体空间中不等圆柱体群的布局为人造卫星再入舱布局的简化模型,属带动力性能约束的Packing优化问题,具有NP难度。本文提出了模式迭换法,用以构造布局拓扑模式,形成初始布局方案;推荐了在此初始布局方案下进行布局寻优的算法;给出了缓解“组合爆炸”的技巧和算例验证。此类问题具有广阔的工程应用前景。

基于质粒DNA匹配问题的分子算法

给定无向图 ,图的最小极大匹配问题是寻找每条边都不相邻的最大集中的最小者 ,这个问题是著名的NP 完全问题 .1994年Adleman博士首次提出用DNA计算解决NP 完全问题 ,以编码的DNA序列为运算对象 ,通过分子生物学的运算操作解决复杂的数学难题 ,使得NP 完全问题的求解可能得到解决 .提出了基于质粒DNA的无向图的最大匹配问题的DNA分子生物算法 ,通过限制性内切酶的酶切和凝胶电泳完成解的产生和最终接的分离 ,依据分子生物学的实验手段 。

生产调度方法的系统研究

在市场竞争和技术进步的驱动下,制造企业不断面临新的生产调度问题.本文评述了已有的调度方法,提出了运用混合遗传算法,解决生产调度问题的方法论.我们把遗传算法与其它随机搜索方法(如模拟退火、列表寻优)、启发式规则及仿真方法结合起来,实现优化调度或满意调度.最后给出一个调度系统原型.

图的最大权团的DNA计算

给定顶点赋权的无向图 ,图的最大权团问题是寻找每个顶点都相邻的顶点子集 (团 )具有最大权 .这个问题是寻找无权图的最大团问题的推广 .图的最大团和最大权团都是著名的NP 完全问题 ,没有非常有效的算法 .1994年Adleman博士首先提出用DNA计算解决NP 完全问题 ,使得NP 完全问题的求解可能得到解决 .本文给出了基于质粒技术的无向图的最大权团问题的DNA算法 ,依据HeadT等的实验手段 ,本文提出的算法是有效并且可行的 .