什么叫多项式时间算法
定义：若存在一个常数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-难的。
延伸阅读
分析算法时间复杂度的两个原则
求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。
这只能基本的计算时间复杂度，具体的运行还会与硬件有关。
什么是P问题NP问题NPC问题三者关系如何
1、P问题
P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。
NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解;P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.
2、NP问题
然而有些问题很难找到多项式时间的算法（或许根本不存在），比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了）。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然，所有的P类问题都是属于NP问题的，但是现在的问题是，P是否等于NP?这个问题至今还未解决。
NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解.
3、NP完全问题
此外请注意，NP问题不一定都是难解的问题，比如，简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题，你能说他很难解么？刚才说了，现在还不知道是否有P=NP或者PNP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信PNP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题（NPC问题，C代表complete）。
NP完全问题是求NP中判定问题的一个子类.NPC问题存在着一个令人惊讶的性质，即如果一个NPC问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！这是因为，每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如前面说的哈米尔顿回路问题就是一个NPC问题。NPC问题的历史并不久，cook在1971年找到了第一个NPC问题，此后人们又陆续发现很多NPC问题，现在可能已经有3000多个了。所以，我们一般认为NPC问题是难解的问题，因为他不太可能存在一个多项式时间的算法（如果存在则所有的NP问题都存在多项式时间算法，这太不可思议了，但是也不是不可能）。类似哈米尔顿回路/路径问题，货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，所以都是难解的问题。
p=np是什么意思
“P/NP问题”,这里的P指在多项式时间(Polynomial)里,一个复杂问题如果能在多项式时间内解决,那么它便被称为P问题,这意味着计算机可以在有限时间内完成计算;NP指非确定性多项式时间(nondeterministic polynomial),一个复杂问题不能确定在多项式时间内解决,假如NP问题能找到算法使其在多项式时间内解决,也就是证得了P=NP。
多项式时间的介绍
多项式时间，就是所需时间是规模的多项式函数，典型的例子是1次函数f(n)=kn+b
史上最难的十大神奇数学题
一、P(多项式时间)问题对NP(非确定多项式时间)问题
二、霍奇(Hodge)猜想
三、庞加莱猜想
四、黎曼假设
五、杨-米尔斯存在性和质量缺口
六、纳维叶-斯托克斯方程的存在性与光滑性
七、贝赫和斯维讷通-戴尔猜想
八、费尔马大定理
九、四色问题
十、哥德巴赫猜想
多项式时间可计算函数
多项式时间，就是所需时间是规模的多项式函数，典型的例子是1次函数f(n)=kn+b
多项式的值为多少时
为5时。
求多项式的值时一般是：
1先把多项式化成最简，2根据指定的字母的值代替相应的字母，3按代数式指明的运算法则和顺序进行计算。
4写出答案即方字母的值是多少时，原代数式的值是多少即可。
