下载文档原格式
世界十大难题1、NP完全问题（NP－C问题）NP完全问题（NP－C问题），是世界七大数学难题之一。
NP的英文全称是Non－deterministicPolynomial的问题，即多项式复杂程度的非确定性问题。
简单的写法是NP＝P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。
NP就是Non－deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。
而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non－deterministicPolynomialcompleteproblem）。
NP完全问题也叫做NPC问题。
2、霍奇猜想霍奇猜想是代数几何的一个重大的悬而未决的问题。
由威廉·瓦伦斯·道格拉斯·霍奇提出，它是关于非奇异复代数簇的代数拓扑和它由定义子簇的多项式方程所表述的几何的关联的猜想，属于世界七大数学难题之一。
二十世纪的数学家们发现了研究复杂对象的形状的强有力的办法。
基本想法是问在怎样的程度上，我们可以把给定对象的形状通过把维数不断增加的简单几何营造块粘合在一起来形成。
3、庞加莱猜想庞加莱猜想（Poincaréconjecture）是法国数学家庞加莱提出的一个猜想，其中三维的情形被俄罗斯数学家格里戈里·佩雷尔曼于2003年左右证明。
2006年，数学界最终确认佩雷尔曼的证明解决了庞加莱猜想。
1904年，法国数学家亨利·庞加莱提出了一个拓扑学的猜想：“任何一个单连通的，闭的三维流形一定同胚于一个三维的球面。
”简单地说，一个闭的三维流形就是一个有边界的三维空间；单连通就是这个空间中每条封闭的曲线都可以连续的收缩成一点，或者说在一个封闭的三维空间，假如每条封闭的曲线都能收缩成一点，这个空间就一定是一个三维圆球。
4、黎曼假设黎曼猜想是关于黎曼ζ函数ζ（s）的零点分布的猜想，由数学家黎曼于1859年提出。
np问题通俗解释
NP问题是指“非确定性多项式时间”问题，也称为不可解问题。
它是计算机科学中的一个重要问题类别。
通俗来说，NP问题是指那些可以在多项式时间内验证是否解
答正确的问题，但尚未找到可以在多项式时间内解决的算法。
也就是说，虽然我们可以在多项式时间内检查一个给定解是否正确，但我们目前还没有找到一种高效的方法来找到一个解。
在计算理论中，NP问题是与P问题相对的一个概念。
P问题
是指可以在多项式时间内解决的问题。
一个经典的例子是旅行商问题。
在旅行商问题中，我们需要找到一条路径，使得旅行商可以经过多个城市，每个城市只到达一次，并且回到起点，同时总路径长度最短。
虽然我们可以在多项式时间内计算出给定路径的总长度，但当前还没有找到一种可以在多项式时间内找到最短路径的方法。
目前来说，还没有找到一种通用的解决NP问题的方法。
因此，研究人员一直在努力寻找解决这些问题的有效算法，或者找到一种方法来证明这些问题不存在多项式时间解决的算法。
这或许是众多OIer最大的误区之一。
你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。
你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。
他们没有搞清楚NP问题和NPC问题的概念。
NP问题并不是那种“只有搜才行”的问题，NPC问题才是。
好，行了，基本上这个误解已经被澄清了。
下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。
接下来你可以看到，把NP问题当成是 NPC问题是一个多大的错误。
还是先用几句话简单说明一下时间复杂度。
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。
不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。
还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。
不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。
同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。
因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。
我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
P NP NPC三者问题阐述1）”P对NP问题”是什么意思？首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。
算法的复杂性是指解决问题的一个具体的算法的执行时间,这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质.比如对于排序问题,如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息,则排序问题的复杂性是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?这个问题至今还未解决。
P问题、NP问题、NPC问题、NP难问题的概念2010-04-15 21:35 | (分类:默认分类)转自/view/3e968900a6c30c2259019e8f.html你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。
你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。
他们没有搞清楚NP问题和NPC问题的概念。
NP问题并不是那种“只有搜才行”的问题，NPC问题才是。
好，行了，基本上这个误解已经被澄清了。
下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。
接下来你可以看到，把NP问题当成是NPC问题是一个多大的错误。
还是先用几句话简单说明一下时间复杂度。
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。
不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。
还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。
不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。
同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。
因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。
离散数学P和NP类问题比较离散数学中的P类和NP类问题是计算机科学中非常重要的概念。
它们帮助我们确定问题的复杂性，并为算法设计和问题求解提供了基础。
本文将比较P类和NP类问题的特点和区别。
一、P类问题P类问题是可以在多项式时间内解决的问题。
也就是说，存在一种算法可以在输入规模的多项式函数内，有效地计算出问题的解。
例如，排序、求和等基本算法属于P类问题。
P类问题具有以下特点：1. 可以在多项式时间内解决。
2. 可以使用确定性算法或非确定性算法进行求解。
3. 可以验证问题的解的正确性。
二、NP类问题NP类问题是可以在多项式时间内验证解的问题。
虽然无法在多项式时间内求解，但可以在多项式时间内验证给定解是否为问题的解。
例如，旅行商问题和背包问题就属于NP类问题。
NP类问题具有以下特点：1. 无法在多项式时间内求解。
2. 可以使用非确定性算法验证解的正确性。
3. 如果一个P类问题可以在多项式时间内约化为NP类问题，那么该P类问题就属于NP类问题。
三、P类和NP类问题的关系P类和NP类问题之间存在许多关系和区别。
1. P类问题是NP类问题的一个子集。
也就是说，所有的P类问题都属于NP类问题。
2. P类问题可以在多项式时间内求解，而NP类问题只能在多项式时间内验证解的正确性。
3. 目前还无法确定P类问题是否等于NP类问题。
这是著名的P与NP问题，其解决将对计算机科学有极其重要的影响。
4. 如果某个NP类问题可以在多项式时间内求解，那么它将成为P 类问题。
这样的问题被称为NP完全问题。
四、NP完全问题NP完全问题是NP类问题中最困难的一类问题。
如果一个NP问题可以在多项式时间内约化为一个已知的NP完全问题，那么该问题本身也属于NP完全问题。
著名的NP完全问题包括旅行商问题、图着色问题和集合覆盖问题等。
NP完全问题具有以下特点：1. 它是NP类问题中最困难的问题。
2. 尚未找到多项式时间内求解NP完全问题的算法，因此被认为无法在多项式时间内求解。
P问题、NP问题、NP完全问题和NP难问题在讲P类问题之前先介绍两个个概念：多项式，时间复杂度。
(知道这两概念的可以⾃动跳过这部分)1、多项式：axn-bxn-1+c恩....就是长这个样⼦的，叫x最⾼次为n的多项式....咳咳，别嫌我啰嗦。
有些⼈说不定还真忘了啥是多项式了。
例如第⼀次看到的鄙⼈→_→2、时间复杂度我们知道在计算机算法求解问题当中，经常⽤时间复杂度和空间复杂度来表⽰⼀个算法的运⾏效率。
空间复杂度表⽰⼀个算法在计算过程当中要占⽤的内存空间⼤⼩，这⾥暂不讨论。
时间复杂度则表⽰这个算法运⾏得到想要的解所需的计算⼯作量，他探讨的是当输⼊值接近⽆穷时，算法所需⼯作量的变化快慢程度。
举个例⼦：冒泡排序。
在计算机当中，排序问题是最基础的，将输⼊按照⼤⼩或其他规则排好序，有利于后期运⽤数据进⾏其他运算。
冒泡排序就是其中的⼀种排序算法。
假设⼿上现在有n个⽆序的数，利⽤冒泡排序对其进⾏排序，①⾸先⽐较第1个数和第2个数，如果后者>前者，就对调他们的位置，否则不变②接着⽐较第2个数和第3个数，如果后者>前者，就对调他们的位置，否则不变③⼀直向下⽐较直到第n-1和第n个数⽐较完，第⼀轮结束。
（这时候最⼤的数移动到了第n个数的位置）④重复前三步，但是只⽐较到第n-1个数（将第⼆⼤的数移动到第n-1个数位置）⑤持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。
举个实例：5,4,3,2,1，对其进⾏排序，先是⽐较5跟4变成4,5,3,2,1，第⼀轮结束后变成43215，可以计算，当对其排序完正好要经过4+3+2+1=10次⽐较，当然这是最复杂的情况，即完全反序。
可以知道对于n个数，⾄多要经过1+2+...+n-1即(n^2-n)/2次⽐较才能排好序。
这个式⼦⾥n的最⾼次阶是2，可知道当n→∞时，⼀次性对其⽐较次数影响很⼩，所以我们把这个算法的时间复杂度⽐作：o(n^2)。
取其最⾼次，可以看出，这是⼀个时间复杂度为多项式的表⽰⽅式。
nphard问题的解释
NP-hard问题是计算复杂性理论中的一个重要概念，它描述了一类特殊的问题。
在解释NP-hard问题之前，我们需要先理解几个基本概念。
P问题：指的是那些其解可以在多项式时间内被验证的问题。
NP问题：指的是那些解的正确性可以在多项式时间内被验证的问题。
NP-complete问题（NPC问题）：既是NP问题也是NP-hard问题的特殊情况，即那些既困难又完整的問題，也就是说，如果一个问题是NP问题，那么它一定可以被多项式时间规约到一个已知的NPC问题上。
NP-hard问题的定义是：一个问题如果是NP-hard的，那么这个问题至少和已知的某个NP-complete问题是等价的。
也就是说，任何一个NP-hard问题都可以在多项式时间内归约（映射）到一个已知的NP-complete问题上。
因此，NP-hard问题是一类非常困难的问题，它们比一般的N P问题更加困难，因为它们不仅要求解的问题能在多项式时间内被验证，而且还要求解的问题至少和某个已知的NPC 问题是等价的。
直观地说，如果我们在解决一个问题时，发现没有任何
已知的有效算法，即便使用现有的最先进的算法也无法在合理的时间内得到解决，那么这个问题就可能是NP-hard的。
例如，著名的“停机问题”（Halting Problem）就是一个典型的NP-hard问题，它问的是给定一个程序和输入，能否在有限时间内判断该程序是否终止。
这个问题已经被证明是NP-hard的，因为它无法在多项式时间内被解决。
总结一下，NP-hard问题是一类非常难以解决的问题，它们至少和已知的某个NPC问题是等价的，这意味着找到这类问题的多项式时间算法非常困难。
