浅谈NP问题
开篇：润墨网以专业的文秘视角，为您筛选了一篇浅谈NP问题范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
np完全问题在科学研究和实际应用中广泛存在，仅仅指出它们的难解性是不够的，更重要的是正面寻求解决方法，其中的关键是算法的设计与分析。
有数学家说过“一个好的问题胜过十个好解答”。因为解答一出，此问题已是到了终点，对不断求创新的人们而言，已不构成挑战。而新的问题是源头活水，能开拓新的境界。多数人都不愿沉醉在好的解答中不断地玩味，而希望找到新的问题，不断地思考、摸索。
了解NP问题
“P=NP?”这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大会上，它是某个1小时讲座的主题。
要说起P和NP是什么东西，得先从算法的多项式时间复杂度谈起，注意，这里面的两个P都是指Polynomial（多项式）。
一个问题的规模指的是输入的总位数，比如一个n个数的排序问题，输入规模就是n。在某些时候，输入规模是值得注意的，比如判定一个数n是否是一个质数这个问题，它的输入规模并不是n，而是log(n)，因为一个数n用大约log(n)位就能表示出来了，这也是为何枚举因子判定素数的算法并不是多项式时间算法的原因。
如果一个算法，能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。注意:这里的多项式时间是指算法运行的步数。一个算法是否是多项式算法，与计算模型的具体的物理实现没有关系，虽然大多数假想的计算模型不可能有任何物理的实现。
P指确定型图灵机上的具有多项式算法的问题集合，NP指非确定型图灵机上具有多项式算法的问题集合，这里N是不确定的意思。
脱离图灵机的概念，就在普通的计算机上看，P问题是指能够在多项式时间求解的判定问题（判定问题指只需要回答是和不是的问题），而NP问题则是指那些其肯定解能够在给定正确信息下在多项式时间内验证的判定问题。比如，要判定一个数是合数，如果给我一个约数，我们就很快判定它就是合数。所以判定一个数是合数的问题属于NP。
NP问题的代表问题之一是售货员旅行问题(traveling salesman problem)。有一个售货员要 汽车到n个指定的城市去推销货物，他必须经过全部的n个城市。现在他有此n城的地图及各城之间的公路距离，试问他应如何取最短的行程从家中出发再回到家中。
NP问题的历史
人们在七十年代开始对NP完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破:基于NP问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。
到了八十年代中，对NP完全问题的研究有了纵向的突破，在许多表面看来并不相关的计算模型之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题，同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工具，并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对NP类的刻划。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代数与编码理论等数学证明技巧。
但是，明显的，目前还没有一个看上去有希望的方向。
数学里最伟大的定理之一―费马大定理，用了数学家纷纷发表了300多年时光。NP问题，作为理论计算机领域最困难的问题，40年时间似乎太短了。
大师的看法
对于NP是否等于P，大家看法不一。在2002年对于100个研究者的调查中，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。
在这份调查报告中，国际上著名的计算机学家对这个问题的看法。
Avi Wigderson:(美国普林斯顿高等研究院教授)我想这个项目还没有成熟，因为关于这个项目的相关知识我们了解的太少了。我唯一可以确定的事情就是，人类所有提出的问题中最重要和最有趣的问题之一，是越来越多的人和资源应该参与其中，才能得到更好的猜想结果。
姚期智:（清华大学教授）很难说何时能够解决这个问题。我的猜想还没有得到学术界的验证，结果很可能是P问题并不等于NP问题，我认为使用数学技术会非常完美的。
可能的结果
从实际应用来说，人们都希望NP=P，因为这意味着很多问题都能有有效的算法，但有些极为诡异的结果也是可能的，人们从这个结果中什么都得不到。
比如某一天人们最终使用某种数学上的技巧证明了NP问题的多项式时间算法的存在性，但并不知道如何找到它――这在数学上是极为可能的，那最终会怎么样呢？
这种情况不会发生，事实上，在NP=P的假设下，人们已经找到了NP完全问题的多项法解法，但这并没有好太多，如果NP=P，很多算法便是一个NP完全问题的多项式时间算法。可是它一点价值都没有，更不用说来解决实际问题了。
经典计算中存在着一大类NP 问题。这类问题在经典计算机上是不能计算的，但是量子计算可以把其中的一部分NP问题变成 P问题，即问题的复杂度随着比特位数的增长以多项式数量级上升。这类问题原则上是可以计算的。
一个具体的例子就是大因数分解，按经典计算复杂性理论，这个问题不存在有效算法。但是如果用量子计算机结合Shor量子算法，这个问题就变成了P问题。
现状
P和NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。而更为重要的是，在无数与计算有关的的学术领域中，NP完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。
计算机与社会科学、自然科学和思维科学等许多学科相互渗透和交叉，形成了许多新的边缘学科和新学科群，正在改变许多传统学科。分子与量子计算机的深入研究和技术难关的攻克，并最终投入运算，必将在政治、经济、军事、文化乃至人类生活的各个方面产生深刻的影响。
最近美国南加州大学Adleman博士应用基于DNA分子计算技术的生物实验方法有效地求解了“哈密顿路径问题”――目前计算机无法解决的NP完备问题。生物分子计算机的研制是基于生物分子的信息处理技术，即生物材料的信息处理功能与生物分子的计算技术。
能以叠加方式存贮信息的量子计算可生成一些真正的随机数，这是传统计算机无能为力的。数学上已证明量子计算可大大加快因式分解的速度。这一证据也吸引人们将注意力集中在根据量子力学原理制造量子计算机上。
计算能力超越图灵机、突破现有的体系结构是计算业界的梦想，不断有报道在DNA计算模型上找到了某NP问题的多项式算法,这应该意味着基于DNA计算模型的P类和NP类的划分会和经典模型有所不同。但是我们仍然希望量子计算能够突破图灵模式，给计算机科学带来一个崭新的世界。