加载中…２１世纪七大数学难题 【每题悬赏100万美元】
(2010-05-24 16:52:11)
标签：
杂谈 |
２１世纪七大数学难题
在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数１３，７１７，４２１可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你它可以因子分解为３６０７乘上３８０３，那么你就可以用一个袖珍计算器容易验证这是对的。不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文·考克（ＳｔｅｐｈｅｎＣｏｏｋ）于１９７１年陈述的。
概述
NP完全问题是不确定性图灵机在P时间内能解决的问题，是世界七大数学难题之一。
NP完全问题排在百万美元大奖的首位，足见他的显赫地位和无穷魅力。
数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是 NP=P？的问题。问题就在这个问号上，到底是NP等于P，还是NP不等于P。证明其中之一，便可以拿百万美元大奖。
这个奖还没有人拿到，也就是说，NP问题到底是Polynomial（意思是多项式的），还是Non-Polynomial，尚无定论。
NP里面的N，不是Non-Polynomial的N，是Non-Deterministic（意思是非确定性的），P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
非确定性问题详解
什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。
这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。
完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。
人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。
解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。
前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。
如果判定问题π∈NP，并且对所有其他判定问题 π∈NP，都有π'多项式变换到π(记为π'∞π)，则称判定问题π 是NP完全的。
对P类，NP类及NP完全问题的研究推动了计算复杂性理论的发展，产生了许多新概念，提出了许多新方法。但是还有许多难题至今没有解决，P=NP?就是其中之一。许多学者猜想P≠NP，但无法证明。
二十世纪的数学家们发现了研究复杂对象的形状的强有力的办法。基本想法是问在怎样的程度上，我们可以把给定对象的形状通过把维数不断增加的简单几何营造块粘合在一起来形成。这种技巧是变得如此有用，使得它可以用许多不同的方式来推广；最终导至一些强有力的工具，使数学家在对他们研究中所遇到的形形色色的对象进行分类时取得巨大的进展。不幸的是，在这一推广中，程序的几何出发点变得模糊起来。在某种意义下，必须加上某些没有任何几何解释的部件。霍奇猜想断言，对于所谓射影代数簇这种特别完美的空间类型来说，称作霍奇闭链的部件实际上是称作代数闭链的几何部件的(有理线性)组合。
霍奇猜想 (Hodge Conjecture)
在非奇异复射影代数簇上, 任一霍奇类是代数闭链类的有理线性组合。
二十世纪的数学家们发现了研究复杂对象的形状的强有力的办法。基本想法是问在怎样的程度上，我们可以把给定对象的形状通过把维数不断增加的简单几何营造块粘合在一起来形成。这种技巧是变得如此有用，使得它可以用许多不同的方式来推广；最终导致一些强有力的工具，使数学家在对他们研究中所遇到的形形色色的对象进行分类时取得巨大的进展。不幸的是，在这一推广中，程序的几何出发点变得模糊起来。在某种意义下，必须加上某些没有任何几何解释的部件。霍奇猜想断言，对于所谓射影代数簇这种特别完美的空间类型来说，称作霍奇闭链的部件实际上是称作代数闭链的几何部件的（有理线性）组合。
黎曼假设、庞加莱猜想、霍奇猜想、贝赫和斯维讷通－戴尔猜想、纳维叶―斯托克斯方程、杨―米尔理论、Ｐ问题对ＮＰ问题被称为21世纪七大数学难题。２０００年５月，美国的克莱数学研究所为每道题悬赏百万美元求解。
如果我们伸缩围绕一个苹果表面的橡皮带，那么我们可以既不扯断它，也不让它离开表面，使它慢慢移动收缩为一个点。另一方面，如果我们想象同样的橡皮带以适当的方向被伸缩在一个轮胎面上，那么不扯断橡皮带或者轮胎面，是没有办法把它收缩到一点的。我们说，苹果表面是“单连通的”，而轮胎面不是。大约在一百年以前，庞加莱已经知道，二维球面本质上可由单连通性来刻画，他提出三维球面(四维空间中与原点有单位距离的点的全体)的对应问题。这个问题立即变得无比困难，从那时起，数学家们就在为此奋斗。
有些数具有不能表示为两个更小的数的乘积的特殊性质，例如，2,3,5,7,等等。这样的数称为素数；它们在纯数学及其应用中都起着重要作用。在所有自然数中，这种素数的分布并不遵循任何有规则的模式；然而，德国数学家黎曼(1826~1866)观察到，素数的频率紧密相关于一个精心构造的所谓黎曼蔡塔函数z(s$的性态。著名的黎曼假设断言，方程z(s)=0的所有有意义的解都在一条直线上。这点已经对于开始的1,500,000,000个解验证过。证明它对于每一个有意义的解都成立将为围绕素数分布的许多奥秘带来光明。
黎曼假设概述
2000年5月24日，美国克雷(Clay)数学研究所公布了7个千禧数学问题。每个问题的奖金均为100万美元。其中黎曼假设被公认为目前数学中(而不仅仅是这7个)最重要的猜想。黎曼假设并非第一次在社会上征寻解答，早在1900年的巴黎国际数学家大会上，德国数学家希尔伯特列出23个数学问题．其中第8问题中便有黎曼假设(还包括孪生素数猜测和哥德巴赫猜想)。
具体概述关于黎曼-希尔伯特问题是：具有给定单值群的线性微分方程的存在性证明。即：关于素数的方程的所有有意义的解都在一条直线上。
有些数具有不能表示为两个更小的数的乘积的特殊性质，例如，2,3,5,7,等等。这样的数称为素数；它们在纯数学及其应用中都起着重要作用。在所有自然数中，这种素数的分布并不遵循任何有规则的模式；然而，德国数学家黎曼(1826~1866)观察到，素数的频率紧密相关于一个精心构造的所谓黎曼蔡塔函数z(s)的性态。著名的黎曼假设断言，方程z(s)=0的所有有意义的解都在一条直线上。这点已经对于开始的1,500,000,000个解验证过。证明它对于每一个有意义的解都成立将为围绕素数分布的许多奥秘带来光明。
1730年，欧拉在研究调和级数：
Σ1/n=1+1/2+1/3+...+1/n.....。(1)
时，发现：
Σ1/n=(1+1/2+1/2^2+...)(1+1/3+1/3^2+...)(1+1/5+1/5^2+...)......=Π(1-1/p)^-1。(2)
其中，n过所有正整数，p过所有素数，但稍加改动便可以使其收敛，将n写成n^s(s>1),即可。如果黎曼假设正确：
Π（x)=Li(x)+O(x^1/2*logx).。(3)
证明了上式，即证明了黎曼猜想。
为什么：
π1/(1-1/P)={1/(1-1/2)}×{1/(1-1/3)}×{1/(1-1/5)}×.......=Σ1/n=1+1/2+1/3+1/4+,,,,。(4)
因为：
1/(1-r)=1+r+r^2+r^3+r^4+......。（5）
所以：
1/(1-1/2)=1+1/2+(1/2)^2+(1/2)^3+(1/2)^4+......
1/(1-1/3)=1+1/3+(1/3)^2+(1/3)^3+(1/3)^4+......
1/(1-1/5)=1+1/5+(1/5)^2+(1/5)^3+(1/5)^4+.......
.......................................
右端所有第一项的“1”相乘得到：“1”；
右端第一行1/2与其它行第一项的“1”相乘得到“1/2";
...................
把所有加起来就是：1+1/2+1/3+1/4+........
在证明素数定理的过程中，黎曼提出了一个论断：Zeta函数的零点都在直线Res(s) = 1/2上。他在作了一番努力而未能证明后便放弃了，因为这对他证明素数定理影响不大。但这一问题至今仍然未能解决，甚至于比此假设简单的猜想也未能获证。而函数论和解析数论中的很多问题都依赖于黎曼假设。在代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设，则可带动许多问题的解决。 素数公式的相关内容
公元前300年，古希腊数学家欧几里得就发现了数论的本质是素数，他自己证明了有无穷多个素数，公元前250年古希腊数学家埃拉托塞尼发明了一种筛法：
（一）“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。（沈康身《自然杂志》1991年11期）。後来人们
（二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1<d≤√N”。（《基础数论》13页，U杜德利著，上海科技出版社）。.
（三）再将（二）的内容等价转换：“若自然数N不能被不大于(根号)√N的任何素数整除，则N是一个素数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。
（四）上面这句话的汉字可以等价转换成为用英文字母表达的公式：
N=p1m1+a1=p2m2+a2=......=pkmk+ak 。(6)
其中 p1，p2，.....，pk表示顺序素数2，3，5，,,,,。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若N<P（k+1）的平方 [注：后面的1，2，3，....，k，（k+1）是脚标，由于打印不出来，凡字母后面的数字或者i与k都是脚标] ，则N是一个素数。
（五）可以把（6）等价转换成为用同余式组表示：
N≡a1(modp1)， N≡a2(modp2)，.....，N≡ak(modpk)。 (7)
例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。 29≡1(mod2)，29≡2(mod3)， 29≡4(mod5)。29小于7的平方49，所以29是一个素数。
以后平方用“*”表示，即：㎡=m*。
由于（7）的模p1，p2，....，pk 两两互素，根据孙子定理(中国剩余定理）知，（7）在p1p2.....pk范围内有唯一解。
例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。
k=2时，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。
k=3时,
---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.|
---------------------|---------|----------|--------|---------|
n=2m+1=3m+1= |--31----|--7, 37-|-13,43|--19----|
n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---|
------------------------------------------------------------
求得了（7，7*）区间的全部素数。仿此下去可以求得任意大的数以内的全部素数。
有人发现埃拉托塞尼筛法的公式【即(6)(7）式】反过来可以推出黎曼猜想的猜想。因为（1）式要求S是复数，（6）（7）式要求n<P(k+1）的平方。只要把两个式子连接起来，就可以研究。现在还没有找到这个纽带。但是已经有共同的内容联系起来。
量子物理的定律是以经典力学的牛顿定律对宏观世界的方式对基本粒子世界成立的。大约半个世纪以前，杨振宁和米尔斯发现，量子物理揭示了在基本粒子物理与几何对象的数学之间的令人注目的关系。基于杨－米尔斯方程的预言已经在如下的全世界范围内的实验室中所履行的高能实验中得到证实：布罗克哈文、斯坦福、欧洲粒子物理研究所和筑波。尽管如此，他们的既描述重粒子、又在数学上严格的方程没有已知的解。特别是，被大多数物理学家所确认、并且在他们的对于“夸克”的不可见性的解释中应用的“质量缺口”假设，从来没有得到一个数学上令人满意的证实。在这一问题上的进展需要在物理上和数学上两方面引进根本上的新观念。
杨-米尔理论
起伏的波浪跟随着我们的正在湖中蜿蜒穿梭的小船，湍急的气流跟随着我们的现代喷气式飞机的飞行。数学家和物理学家深信，无论是微风还是湍流，都可以通过理解纳维叶－斯托克斯方程的解，来对它们进行解释和预言。虽然这些方程是19世纪写下的，我们对它们的理解仍然极少。挑战在于对数学理论作出实质性的进展，使我们能解开隐藏在纳维叶－斯托克斯方程中的奥秘。
数学家总是被诸如x^2+y^2=z^2那样的代数方程的所有整数解的刻画问题着迷。欧几里德曾经对这一方程给出完全的解答，但是对于更为复杂的方程，这就变得极为困难。事实上，正如马蒂雅谢维奇(Yu.V.Matiyasevich)指出，希尔伯特第十问题是不可解的，即，不存在一般的方法来确定这样的方法是否有一个整数解。当解是一个阿贝尔簇的点时，贝赫和斯维讷通－戴尔猜想认为，有理点的群的大小与一个有关的蔡塔函数z(s)在点s=1附近的性态。特别是，这个有趣的猜想认为，如果z(1)等于0,那么存在无限多个有理点(解)，相反，如果z(1)不等于0,那么只存在有限多个这样的点。
简介
BSD猜想，全称“波奇和斯温纳顿—戴雅猜想”。属于世界七大数学难题之一，2000年初美国克雷数学研究所的科学顾问委员会选定了七个“千年大奖问题”，克雷数学研究所的董事会决定建立七百万美元的大奖基金，每个“千年大奖问题”的解决都可获得百万美元的奖励。克雷数学所“千年大奖问题”的选定，其目的不是为了形成新世纪数学发展的新方向，而是集中在对数学发展具有中心意义、数学家们梦寐以求而期待解决的重大难题。
猜想内涵
数学家总是被诸如x^2+y^2=z^2那样的代数方程的所有整数解的刻画问题着迷。欧几里德曾经对这一方程给出完全的解答，但是对于更为复杂的方程，这就变得极为困难。事实上，正如马蒂雅谢维奇(Yu.V.Matiyasevich)指出，希尔伯特第十问题是不可解的，即，不存在一般的方法来确定这样的方法是否有一个整数解。当解是一个阿贝尔簇的点时，贝赫和斯维讷通－戴尔猜想认为，有理点的群的大小与一个有关的蔡塔函数z(s)在点s=1附近的性态。特别是，这个有趣的猜想认为，如果z(1)等于0,那么存在无限多个有理点(解)，相反，如果z(1)不等于0,那么只存在有限多个这样的点。BSD猜想是有可能破解的。
我们再来看看和BSD猜想同样被列为“世界七大数学难题”的其他问题都解决得怎么样了：
黎曼假设：很多人攻关，没看到希望
霍奇猜想：进展不大
杨—米尔理论：太难，几乎没人做
P与NP问题：没什么进展
纳威厄—斯托克斯方程：离解决相差很远
庞加莱猜想：2006年被确认由俄罗斯数学家格里戈里·佩雷尔曼最终证明，他也因此在同年被授予菲尔兹奖，但并未现身领奖
___________________________________________
喜欢
0
赠金笔