《对p和np问题的介绍》由会员分享，可在线阅读，更多相关《对p和np问题的介绍（10页珍藏版）》请在金锄头文库上搜索。
1、对P和NP问题的介绍,P/NP问题是史提芬古克于1971年首次提出 ，P/NP问题是克雷数学研究所高额悬赏的七个千禧年难题之一，同时也是计算机科学领域的最大难题，关系到计算机完成一项任务的速度到底有多快。 2010年8月7日，来自惠普实验室的科学家Vinay Deolalikar声称已经解决了“P/NP问题” ，并公开了证明文件。但其后被其他学者发现有错误。,P问题、NP问题与NPC问题,1 P问题（Polynomial ） P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内
2、解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。 2 NP问题（Non-deterministic Polynomial ） NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解 ，也可以说是这些问题可以在非确定性多项式时间内解决，它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决 。,3 NP完全问题（NPC） NP完全问题是求NP中判定问题的一个子类，是最不可能被化简为P的决定性问题的集合 .NP
3、C问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题，所以NPC是解决P/NP问题的关键。,注：多项式时间 多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。 以数学描述的话，则可说m(n) = O(n)，此n为一常数值（依问题而定）。 数学家有时把“如多项式时间长的算法”视为快速计算，相对应的是超多项式
4、时间，表示任何多项式时间的输入数目只要够大，超多项式时间所需的解题时间终究会大大超过任何多项式时间的问题。,计算机科学家为什么认为P NP？,多数计算机科学家相信PNP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了（Karp的21个NP完全问题，在最早发现的一批中，有所有著名的已经存在的问题）。进一步地，P = NP这样的结果会导出很多惊人的结果，那些结果现在被相信是不成立的 也有这样论证的：问题较难求解（NP）但容易验证（P），这和我们日常经验是相符的。 从另一方面讲，某些研究者认为我
5、们过于相信P NP，而应该也去寻找P = NP的证明。例如，2002年中有这样的声明：,倾向PNP的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点 摩西瓦迪（Moshe Vardi），莱斯大学 过分依赖某种投机的猜测不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。 Anil Nerode, 康奈尔大学,证明的难度,虽然百万美元的奖金和大量投入巨大却没有实质性结果的研究足以显示该问题是困难的，还有一些形式化
6、的结果证明为什么该问题可能很难解决。 最常被引用的结果之一设计神喻。假想你有一个魔法机器可以解决单个问题，例如决定一个给定的数字是否为质数，但可以瞬间解决这个问题。我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题，P = NP和P NP二者都可以证明。这个结论的后果是，任何可以修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在相对化）。 如果这还不算太糟的话，1993年Razborov和Rudich证明的一个结果表明，给定一个特定的可信
7、的假设，在某种意义下“自然”的证明不能解决P = NP问题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。,假如P=NP，世界将会怎样？,P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。科学家们普遍认为PNP是有原因的，让我们来看一看，如果哪一天科学家证明了P=NP，那这个世界将会变得怎样？,已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；
8、同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。 算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。 一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。 困扰人类已久的自然语言处理问题将被一举攻破。考虑这样一个最优化问题：输入一大批语句样本，它们有的符合语法，有的不符合语法；寻找一个最简单的算法，将这些语句输入这个算法时，算法能正确得出它是否符合语法。,类似地，所有人工智能问题都将得到解决。我们只需要向计算机提交足够多的情境以及与之对应的正常人反应，计算机就可以找出一种能正确生成出这些反应的最简算法，完全模仿人类的行为。 数学证明可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单，一切错误的猜想都将瞬间被推翻。事实上，寻找一个数学证明和验证一个证明的正确性也变得同样简单，因此一切正确的命题也能够瞬间找到一个最简的证明。 发明任何新的密码算法都是徒劳 。计算机可以根据一大批明文密文样本推算出生成密文的算法（只要这个算法是多项式的）。现有的密码学体系彻底崩溃。,
