多项式时间指的是什么（什么是伪多项式时间算法）

本文目录

• 什么是伪多项式时间算法
• P对NP问题的简介
• 谁证明了p等于np
• 什么叫多项式时间算法
• 大O符号基础
• 什么是NP问题，NP-complete和NP-hard问题
• 什么是多项式时间

什么是伪多项式时间算法

想要理解“伪多项式时间”，我们需要先给出“多项式时间”的一个清楚的定义。
对于“多项式时间”，我们的直观概念是时间复杂度,其中是一常数。比如，选择排序的时间复杂度是，是多项式时间；暴力解决TSP问题的时间复杂度是，不是多项式时间。我们称这种时间复杂度为“传统时间复杂度”。
我们通常认为传统时间复杂度中的变量表示数据的输入规模。比如，选择排序中，指待排序数组中元素的个数；TSP问题中表示图中节点的数量。但是，这些所谓的输入规模，仅仅是直观的定义，并不足够严谨。为了标准化这些，在计算标准时间复杂度时，我们给出了输入规模的标准定义：
一个问题的输入规模是保存输入数据所需要的bit位数。
比如，如果排序算法的输入是一个32-bit整数 数组，那么输入规模就是，是指数组中元素的个数。对于一个带有个节点、条边的图，需要的bit位数就是。
了解了输入规模的定义，我们来看“多项式时间”的标准定义：
对于一个问题，在输入规模为x的情况下，如果一个算法能够在O()时间内解决此问题，则我们称此算法是多项式时间的，其中为一常数。
当我们处理一些图论、链表、数组、树等问题时，这个标准定义下的多项式时间和我们传统的多项式时间相差无几。比如，用选择排序对元素个数为的数组进行排序时，传统时间复杂度为。输入规模，因此，得到的标准时间复杂度是，仍然是多项式时间。

P对NP问题的简介

P对NP问题是Steve Cook于1971年首次提出。“P/NP问题”，这里的P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算；NP指非确定性多项式时间（nondeterministic polynomial），一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。比NP问题更难的则是NP完全和NP-hard，如围棋便是一个NP-hard问题。2010年8月7日，来自惠普实验室的科学家Vinay Deolalikar声称已经解决了“P/NP问题” ，并公开了证明文件。

谁证明了p等于np

谁证明了p等于np如下：

斯蒂文·考克于1971年提出的。

2000年5月，著名的克雷数学研究所提出了“世界七大数学难题”，其中的第一个问题便是NP完全问题，它所探讨的是P=NP是否成立。

P是否等于NP，对于21世纪的人类来说至关重要，因为这个神秘的问题正处于计算机科学与数学的交汇处。

事实上，P=NP问题是“计算复杂性理论”的一部分，它所讨论的是计算机处理能力的极限。
我们知道，计算机的工作必须依赖于算法，也就是一系列需要执行的命令。

在完成某些任务时，计算机只需要几微秒就可以实现，但另一些，以目前的计算机算法处理速度则可能需要几十亿个世纪。

首先，P/NP问题是什么？P/NP问题不仅是一个数学问题，同时也是困扰了计算机科学家、经济学家、甚至哲学家多年的问题，是世界级数学难题之一，也被称为千禧年七大数学难题之首。

P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算NP指非确定性多项式时间。

（nondeterministic polynomial），一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P=NP。

什么叫多项式时间算法

定义：若存在一个常数C，使得对于所有n》=0，都有|f(n)|
《=
C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。
　　例如：时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指时间算法。
　　一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。
　　一个问题如果没有找到多项式时间算法，那么直觉上它是“难解”的，但又往往无法证明多项式时间算法的不存在性。由于在寻找有效算法上的失败未必一定意味着这样的算法不存在，这就给理论工作者带来了一个难题：一方面证明一个问题不存在多项式时间算法是困难的，至今尚未给出；另一方面有越来越多的问题无法给出多项式时间算法。同时，理论工作者又渴望解决此难题。为此，在20世纪70年代提供了一个漂亮的理论，它把这种失败归结为一个深刻的数据猜想，这个理论就是NP-完全性理论。
　　定义：给定一个判定问题，如果存在一个算法，对任何一个答案为“是”的实例I。该算法首先给出一个猜想，该猜想规模不超过I的输入长度的某个多项式函数，且验证猜想的正确性仅需多项式时间，则称该问题属于NP类。
　　定义：如果NP类中所有问题都可以多项式时间归约到NP类中某个问题x，则称x是NP-完全问题。
　　定义：如果某优化问题x的判定问题是NP-完全的，则称问题x是NP-难的；如果x的判定问题是强NP-完全的，则称x是强NP-难的。

大O符号基础

大O符号 (Big O notation)， 又称渐进符号，是用于描述函数的渐近行为的数学符号。它是指用另一个(通常更简单的)函数来描述一个函数数量级的渐进上界。

在n趋于无穷大时，这些函数从上到下增长越来越快。
即在用于描述时间复杂度时，随着问题规模的增大，从上到下所需要消耗的时间越来越多。

相关概念：
多项式时间 (Polynomial time)即指一个问题的计算时间m(n) = O(n ）， k 为常量值。
数学家有时把“如多项式时间长的算法”视为快速计算。

超多项式时间 即当计算规模足够大，解题时间将大大超过任何多项式时间的问题。

相关符号：
大Ω符号 ：大O符号表示函数在增长到一定程度时总小于某函数的常数倍，大Ω符号与大O符号正好相反，表示总大于。即：

大Θ符号 是大O符号和大Ω符号的结合。即：

References:

什么是NP问题，NP-complete和NP-hard问题

什么是NP问题
概念1:
在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。
概念2:
多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
以数学描述的话，则可说m(n) = O(n)，此n为一常数值（依问题而定）
拿推销员旅行问题为例，假设推销员亨利有向6个城市推销公司产品的任务，并规定了一个旅行预算。他手中有一张航班票价表，他要从A城开始走遍图中的6个城市后返回A城，并且不超出预算，请你帮他找出应走的路线。如果给出的预算宽裕，则任务很简单；如果预算比较紧张，你就得认真设计路线了。你得考虑每一种可能的次序，以使旅费最少。
而NP问题中最困难的问题称之为NP完全问题(NP-complete)，已经证明的包括：电话网络的最优几何设计、格子棋的最佳走法。根据库克定理，任意一个NP完全问题如果能够在多项式时间内解决，则所有的NP问题都能在多项式时间内解决，而至今这一问题仍无答案。
什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。
这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间（多项式时间： 运行时间最多是输入量的多项式函数）内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。
完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。
解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。
什么叫做NP问题，什么叫做NPC问题?
首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。算法的复杂性是指解决问题的一个具体的算法的执行时间，这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质。比如对于排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O(n^2)，快速排序平均情况下是O(nlgn)等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。
为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？。。。从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。
如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。
然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。注意，NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？ 刚才说了，现在还不知道是否有P=NP或者P《》NP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信P《》NP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。
类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。

什么是多项式时间

就是问题需要的时间（复杂度）与问题的规模之间是多项式关系。
举个例子，现在从n阶图中找两点的最短路径，复杂度为n^2级别（即O(n^2)，O是大写欧），而n^2对于n是多项式（单项式当然也算），这就称为是多项式复杂度，或者多项式时间，其中问题（算法）的规模是n。如果某一个算法的规模是n，但是复杂度比如是2^n，写不成n的多项式，那就不是多项式时间。