基于图灵模型的P=？ NP问题分析

P=？NP问题是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型,对P=？NP问题的研究现状、P=NP／P≠NP 证明方法、NPC问题求解方法及研究进展进行阐述。     

P vs. NP问题研究状态及其对密码学的意义

介绍P vs.NP问题的研究状态以及P vs.NP问题的研究对于密码学的意义。主要内容包括关于证明P≠NP的主要研究方法和相关工作,关于证明P=NP的主要研究方法和相关工作,关于求解NP完全问题的相关方法,以及P vs.NP问题研究与密码学的关系。由于现代密码学建立在未知密钥情况下不存在有效的算法将明文消息从密文中提取出来的假定之上,因此安全加密算法存在的一个必要条件是P≠NP。如果P=NP,根据Cook的观点,现代密码体制将崩溃。依据P=NP的假定,给出一个可能的密码分析模型。     

改进的最优顶点覆盖贪心边近似算法

最优顶点覆盖问题是6个基本的NP完全问题之一，无法在多项式时间内得到最优解，除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时，证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。     

NP-完全问题汇编

在计算复杂性理论中已发现了几百个难题,著名的货郎担问题就是其中一例。这一类问题都是问:是否存在有解某一特定的大量问题的实际可行的算法(用专门术语来说,即是否有计算时间多项式有界的算法)?现在已经知道的是,对非决定的机器而言,这些问题是有计算时间多项式有界的算法的,即是所说的复杂性属于NP类的问题,而且是NP类中难度最大的问题(用专门术语来说,是具有NP完全性的问题)。但对于决定的机器(实际计算机都是决定的机器)而言,是否有计算时间多项式有界的算法(即计算机上实际可行的算法)呢?目前还不知道。这一类问题具有下列的重要性质:只要能找到其中一个特定问题的实际可行的算法,就可以找到其他几百个问题的同类算法,而如果能证明其中某一个问题没有实际可行的算法,那么也就证明了其它几百个问题都没有这样的算法。由于这一类问题在许多数学分支(如代数、数论、数理逻辑和图论等)和工程技术中出现,而只要解决了其中的一个就解决了同类的千百个问题,这类问题一旦解决将有无比重要的理论意义和实际意义。这就是计算复杂性理论中所说的P=?NP的问题,这个问题被许多有关的科学工作者认为是当前计算机科学中最大的未解决的问题之一(目前绝大多数有关的科学工作者的猜测是:答案是否定的,即P≠NP)。美国贝尔电话公司研究所的研究员Garey 和 Johnson二人在1979年出版了《计算机与难解性——一本NP完全性理论的指南》(Computers and Intractability:AGuide to the Theory of NP Completeness)一书。他们搜集了到1978年夏天为止已发现的三百个具有NP完全性的问题,索编成这书的附录。这一问题索编对于从事这方面研究工作的人是不可缺少的参考资料。     

P≠NP假设下NP-NPC-P中自然问题的一个候选者

1975年,Lander证明在P≠NP假设下存在一个语言属于NP-NPC-P(NPI).但Lander给出语言并不是一个自然的语言因在该语言的构造中需运行所有多项式时间的图灵机.迄今为止,还没有自然的语言被证明在P≠NP假设下属于NPI,并且在P≠NP假设下寻找一个属于NPI的自然语言是一个重要的未解决问题.作者部分解决了此长期未解决的问题.定义了2+f(m)-HAST模型.基于该模型,给出了在P≠NP假设下NP-NPC-P中自然问题的一个候选者.已证明在P≠NP假设下它不属于NPC并且在更强但合理的假设下它的确属于NPI.     

网格计算资源调度算法研究

如何将网格这个复杂环境中的资源进行有效调度，是一个NP问题。并行遗传算法被证明是解决这类问题的有效算法，同时并行遗传算法有“早熟”和慢速收敛等缺点。为了克服其缺点，该文引进蚁群算法思想，将两个算法结合起来，充分发挥各自的优势，该算法能更有效地解决网格计算资源分配的问题。     

基于变元加权的一种求解SAT问题的新方法

研究合取范式可满足性的SAT问题作为一个NP完全问题,在计算机科学及组合优化问题领域中有着中心课题的重要地位。由于其NP问题的性质决定了它尚无通用快速的完全算法,因此基于“实验算法学”的思想,按照平均性态而不是最坏情况性态的原则,对具有启发式策略的不完全算法的研究成为近年来大家关注与努力的焦点。该文正是立足于此,提出了“加权消元”这一种全新而且高效的算法。     

基于遗传算法的网格计算资源调度策略

如何将网格这个复杂环境中的计算资源进行有效调度,是一个NP问题。遗传算法被证明是解决这类问题的有效算法,同时遗传算法有“早熟”和慢速收敛等缺点。为了克服其缺点,提出一种新的并行遗传算法,采取避免近亲繁殖的交叉策略和保护优秀个体的方法,提高算法搜索能力和收敛速度。仿真结果表明该算法能有效地解决网格计算资源分配问题。     

带多约束条件的最优路径选择算法研究

传统的启发式算法把NP完全问题转化成一个能够在多项式时间内求解的P问题,却不能保证每次都得到最优路径。利用拉格朗日松弛法把该问题转换成一个P问题,利用次梯度算法来确定最优解,在降低算法时间复杂度的同时提高最优路径查找的成功率。通过实验和分析,该算法的有效性得到了验证,可以应用在地理信息系统和通信网络中。     

观察数学现象的“望远镜”

有了望远镜,我们能看清楚远处看不清、看不到的景物。几何画板就是一个观察数学现象的“望远镜”,它能帮助我们思考,“延伸”大脑的功能。我们不知道数学家是如何发现“三角形的垂心H、重心G、外心W在一条直线上,并且HG=2GW”这个结论的,至少现在我们知道当初如果有了《几何画板》,这件事要好办得多。这是《数学通报》“数学问题”栏目的1167题:P是     

多NP万兆级硬件防火墙简介

联想网御公司用一年半的时间,充分挖掘高端NP快速分组特点,突破硬件平台“按需配置”障碍,解决多NP协同工作难题,推出网御SuperV-Ⅱ防火墙,填补了国产万兆级防火墙的空白。这一成功实践,必将成为中国信息安全产业技术致胜之路的里程碑。     

可满足性问题生物芯片DNA算法

可满足性问题是经典的NP问题。可满足性问题在硬件测试、人工智能、电路设计方面都有重要的应用。首先对可满足性问题进行研究,报告了DNA计算关于可满足性问题的研究现状,然后介绍了微流路芯片高压凝胶电泳,给出了解决可满足性问题的解法。最后通过一个实例验证了算法的可行性。给出的算法操作简单,出错率低。算法只需要芯片电泳,不需要构造探针,也不需要荧光标记。本文对解决其他NP问题具有很好的借鉴意义。     

应用改进微粒群算法求解QoS路由技术问题

高速多媒体网络中的路由问题是有QoS约束的路由问题,多受限的路由问题是一个NP完全问题.本文提出了一种解决多受限QoS路由问题的改进微粒群算法.该算法利用记忆库来动态调整惯性权重值,加快了算法的收敛速度.同时结合进化、灾变机制避免了算法陷入局部极值的问题.在列出改进算法的具体步骤基础上,通过实例证明了算法的有效性,使多受限QoS路由优化问题很好地得到了解决.     

Markov决策过程的蚁群规划算法

在智能规划问题上,寻找规划解都是NP甚至NP完全问题,如果动作的执行效果带有不确定性,如在Markov决策过程的规划问题中,规划的求解将会更加困难,现有的Markov决策过程的规划算法往往用一个整体状态节点来描述某个动作的实际执行效果,试图回避状态内部的复杂性,而现实中的大量动作往往都会产生多个命题效果,对应多个命题节点。为了能够处理和解决这个问题,提出了映像动作,映像路节和映像规划图等概念,并在其基础上提出了Markov决策过程的蚁群规划算法,从而解决了这一问题。并且证明了算法得到的解,即使在不确定的执行环境下,也具有不低于一定概率的可靠性。     

Some structural properties of SAT

The following four conjectures about structural of SAT are studied in this paper.(1) SAT∈P^SPARSE∩NP;(2)SAT∈SRTDtt;(3)SAT∈Ptt^bAPP;(4)FPtt^SAT=FTlog^SAT.It is proved that some pairs of these conjectures imply P=NP ,for example,if SAT∈P^SPARSE∩NP and SAT∈Ptt^bAPP,or if SAT∈SRTDtt and SAT∩PttbAPP,then P=NP.This improves previous results in literature.     

关于NP结构的研究

本文旨在在讨论 NP 结构的问题。多项式归约≤P M、图灵归约≤P T,及γ-归约≤~(Np)_r的概念是重要的,它们分别由 Karp、Cook 及 Adelman 和 Manders所引入。根据现有的情况我们提出了三个猜想。在猜想1:P≠NP 和猜想2:NP≠co-NP 的前提下讨论了 NP 结构。最后讨论了 NPC 的 P 同构问题,在此基础上给出了第三个猜想:所有 NP 完全的问题都是 P 同构的,猜想2,3都蕴涵了猜想1。     

解决VB6的乱码问题

长期以来,VB6页签内的乱码问题一直困扰着VB程序员。那些怪模怪样的“汉字”,给编程带来极大的不便。我本人也为之大伤脑筋,一直在寻求着解决的办法。 这一日,为解决另一个不兼容的问题,我试着将“控制面板\区域设置”中的“中文(中国)”改为“英语(美国)”,结果那个问题没有得到解决,我未加理睬,接着启动了     

P与NP问题研究

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

相对于单元素语言的多项式时间谱系的研究

通过讨论相对于单元素语言的多项式时间谱系,得到了Ⅱp1(A)∈△1的一个充分条件,进而研究了多项式时间谱系中的类∑p1内的单元素语言T与计算复杂性理论中的重要相对化语言类CO-NP(T)、P(NP)、∑p t-1(T)、△p1、NP(T)、NP等之间的联系.     

计算角形块结构问题主规划初始解的一个方法

一、引言 对于角形块结构线性规划问题,在应用Dantzig-Wolfe分解方法进行计算时,先要确定问题的主规划的一个初始基本可行解。有关这一问题,在[2]中已经有了粗略的讨论。 本文提出解决这一问题的算法,它适用于原来问题的主约束具有“≤”,“≥”和“=”的一般情况,这一算法的基本思想是先在每一子约束中选取一个基本可行解,并把它们代入主约束的方程组中,对不满足主约束的方程,引入相应的非负偏差变量,并继续极小化所有偏差变量的和。如果这一极小化问题已经满足最优性条件且偏差变量之和为零,我