NP完全问题研究及前景剖析

P vs.NP是理论计算机领域最重要的课题之一,而其中的核心是NP完全问题.由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误.主要是:NP、NP完全概念理解谬误,确定性及非确定性图灵机的概念模糊不清,P与NP关系的误读,NP问题研究方向的误导等.本文分析了这些谬误,并揭示了相关概念的实质.通过不同角度多方位分析,对NP完全问题可能的解决途径和研究方向,提供了启发式思路.

CAM中一类新的NP完全问题

本文提出了计算机辅助制造(CAM)中的一类作业调度问题并证明了它的NP完全性。

DNA计算方法在求解NP完全问题中的应用

DNA计算是应用分子生物技术进行计算的新方法.本文主要介绍了DNA计算的基本思想及解决NP完全问题的DNA模型,讨论了目前DNA计算存在的问题和今后的发展方向.

d-正则(k,s)-SAT问题的NP完全性

研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.

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

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

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

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

空间方向关系推理计算的NP完全性研究

空间方向关系推理问题的NP完全性证明是基于两个重要的变换基础之上的,其中一个变换是把空间方向关系推理问题变换为一个限定满足问题,基于这种变换,空间方向关系推理问题中的变量和值域相应地变换为限定满足问题中的空间目标和方向关系限制;另一个变换是从不全等3可满足问题到方向关系限定满足问题,基于这种变换,3可满足问题实例中的变量可以变换为两个方向关系限制.为此,一个满足所有目标方向关系限制的空间结构可以建立,从而可以证明空间方向关系推理问题的NP完全性性质.

表的等价性的NP完全性的讨论

本文给出了表的等价性判定的一些结果：三元可满足性问题、表达式的ＮＰ完全性、表的ＮＰ完全性，还给出了函数依赖对表的影响、强等价性的复杂性的一些讨论。为对表的进一步研究指出了方向。

部分赋值一阶逻辑公式的条件求值——NP完全性及在特定情况下的求解

部分赋值的一阶逻辑公式的条件求值问题是在关系数据库应用,尤其是在分布式环境下应用中经常遇到的问题。此问题在一般意义下的解是NP完全的。本文首先证明此问题的解存在的充要条件,从而推知其NP完全性。然后给出该问题在一种特定情况下的求解方法。

NP完全性理论中关于集合恰当覆盖的一个证明

NP完全性理论是国际上数学与计算机科学理论研究的新领域.本文证明了NP完全性理论中关于集合恰当覆盖的一个结论,充实了NPC理论中关于集合覆盖的论证.

MSP问题NP完全性研究

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

不仅要正确而且还要有效——NP完全性理论简介

求解问题的方法正确与否当然是相当重要的,但仅有正确性还不够因为一个正确的无效方法仍是无用的,故方法的有效性也是很重要的。这一点直到本世纪七十年代才被人们真正认识。1971年美国人S.A.Cook在《定理证明过程的复杂性》中证明了第一个NP完全问题,从而为NP完全性理论奠定了基础。从那时起,这一理论一直是数学和计算机科学工作者研究的重要领域之一。算法就是求解问题的一种方法的实现。

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

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

一个构造的Np完全问题及其复杂性下界猜测

本文提出一个构造的 Np 全全问题 DHC。该问题由(?)郎担问题和哈密顿回路判定问题导出,导出 DHC 的基本思想是试图使求解与 DHC 相应的最优化问题必须与输入无关地在图 G 的全部 H 回路间进行,从而使求解该最优化问题的算法的复杂性至少与图 G 中包含的哈密顿回路(即 H 回路)的条数有相同的数量级。根据 DHC 同与之相应的最优化问题的 Np 等价性(见定理2、定理3)可推断求解 DHC 的任何解定型算法的时间复杂性下界,按照本文的思想,不难构造出一大批类似的 Np 完全问题。本文提出的猜测,可能是对近来由于六大难题之一的子图同胚问题获得解决,更多的人开始由以前的试图证明 Np(?)P 转而考虑 Np=P 的反动。

NP完全问题多项式时间算法研究

本文从代数及组合两个方面论证了NP完全问题存在多项式时间算法 .以往利用线性规划 (LP)技术来分析NP完全问题中的TSP问题 ,因其存在子环游问题 ,从而使问题得不到有效解决 .文中发展一分层网络 ,在求解TSP问题时 ,存在另一类(不完全 )子环游问题 .但两模型允许解集的交集避免了两类子环游基本可行解 ,从而使TSP问题可利用LP技术多项式时间内得以解决 ,同时给出了求哈密尔顿回路的多项式标记证明方法 ,开创了NPC问题研究的新局面 .

离散数学中NP完全问题的DNA计算

随着数学研究逐渐深入,对于离散数学问题探究越来越多。离散实现是数学领域中的重要分支,在离散数学中包含着很多NP完全问题,为了有效的解决这些完全问题,需要借助DNA计算方式。目前DNA计算已经成为了数学、生物、化学乃至计算机科学领域中的重点研究对象。基于此,在本文中对离散数学中NP完全问题的DNA计算进行研究。

若干NP完全问题的特殊情形

讨论了图算法中若干ＮＰ完全问题在所给的图是一棵树时的特殊情形－ 利用树结构的前序编号表示法提出了解树的最大独立集问题。

基于粒子群优化算法在NP难问题中的应用研究

为解决NP难问题中算法应用领域划分问题,分别运用不同算法对不同问题规模的TSP问题进行求解,寻求最优路径规划.采用随机数据来最大化模拟实际情况,设置了5、10、15、20、30和100个随机城市坐标点,分别采用PSO算法、C-PSO算法、GA算法和ACO算法进行求解,求解一条经过各城市且一次的旅行最低费用的路线,分析比较四种算法的鲁棒性与实效性.结果表明:基于C-PSO算法在NP难问题中的具有良好鲁棒性和较短的运行时间,在问题规模小时,可以采用PSO算法和ACO算法;在问题规模大时,可以采用C-PSO算法.

电力系统NP难问题全局优化算法的研究

通过对现有的 NP难问题求解方法的分析 ,结合非确定性图灵机理论 ,提出基于随机化技术的方法是求解 NP难及 NP完全问题惟一有效途径的猜想。在现有的随机化方法中具有多点搜索特性的遗传算法具有最强的全局搜索能力 ,其局部精细寻优能力差的缺陷应通过专门的局部优化算法来补偿 ,即利用具体问题的特点开发面向问题的遗传算法。提出了开发新的高效全局优化算法的指导思想 :多点随机化全局搜索策略 +面向问题的局部寻优算法 =最有效的全局优化算法。

P与NP问题研究

P与NP问题被列为七大世界数学难题之首,由于其相关概念抽象而复杂,许多该领域的学生学者,对其相关概念的理解存在谬误,不少已发表的研究论文都体现了这一谬误。用中文通俗讲解到底什么是P和NP问题以及它们的关系,透过抽象的定义揭示其本质。列举一些科研论文上常见的对P和NP问题理解上的谬误,通过分析揭示其错误实质。同时并对解决这一问题可能的研究方法作一综述,对研究前景做一展望,为在该方向上学习和研究的学生学者,提供有价值的参考。由于文中包括:对复杂抽象的概念进行通俗而深入的剖析,对已有的研究进展进行摘要概括,对未来可能的研究方法和研究路线进行综述和分析,故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益。