1、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,但无法证明。
2、郝治(Hodge) 猜想
也叫霍奇猜想(Hodge Conjecture):在非奇异复射影代数簇上, 任一霍奇类是代数闭链类的有理线性组合。
二十世纪的数学家们发现了研究复杂对象的形状的强有力的办法。基本想法是问在怎样的程度上,我们可以把给定对象的形状通过把维数不断增加的简单几何营造块粘合在一起来形成。这种技巧是变得如此有用,使得它可以用许多不同的方式来推广;最终导至一些强有力的工具,使数学家在对他们研究中所遇到的形形色色的对象进行分类时取得巨大的进展。不幸的是,在这一推广中,程序的几何出发点变得模糊起来。在某种意义下,必须加上某些没有任何几何解释的部件。霍奇猜想断言,对于所谓射影代数簇这种特别完美的空间类型来说,称作霍奇闭链的部件实际上是称作代数闭链的几何部件的(有理线性)组合。
3、庞加莱(Poincare) 猜想
在一个三维空间中,假如每一条封闭的曲线都能收缩到一点,那么这个空间一定是一个三维的圆球。但1905年发现提法中有错误,并对之进行了修改,被推广为:“任何与n维球面同伦的n维封闭流形必定同胚于n维球面。”
如果你认为这个说法太抽象的话,我们不妨做这样一个想象:
我们想象这样一个房子,这个空间是一个球。或者,想象一只巨大的足球,里面充满了气,我们钻到里面看,这就是一个球形的房子。
4、黎曼(Rieman )假设
有些数具有不能表示为两个更小的数的乘积的特殊性质,例如,2,3,5,7,等等。这样的数称为素数;它们在纯数学及其应用中都起着重要作用。在所有自然数中,这种素数的分布并不遵循任何有规则的模式;然而,德国数学家黎曼(1826~1866)观察到,素数的频率紧密相关于一个精心构造的所谓黎曼蔡塔函数z(s)的性态。著名的黎曼假设断言,方程z(s)=0的所有有意义的解都在一条直线上。这点已经对于开始的1,500,000,000个解验证过。证明它对于每一个有意义的解都成立将为围绕素数分布的许多奥秘带来光明。
在证明素数定理的过程中,黎曼提出了一个论断:Zeta函数的零点都在直线Res(s) = 1/2上。他在作了一番努力而未能证明后便放弃了,因为这对他证明素数定理影响不大。但这一问题至今仍然未能解决,甚至于比此假设简单的猜想也未能获证。而函数论和解析数论中的很多问题都依赖于黎曼假设。在代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设,则可带动许多问题的解决。
5、杨-米尔斯 (Yang-Mills) 理论
又称规范场理论,是研究自然界四种相互作用(电磁、弱、强、引力)的基本理论,是由物理学家杨振宁和R.L.米尔斯在1954年首先提出来的。它起源于对电磁相互作用的分析,利用它所建立的弱相互作用和电磁相互作用的统一理论,已经为实验所证实,特别是这理论所预言的传播弱相互作用的中间玻色子,已经在实验中发现。杨-米尔斯理论又为研究强子(参与强相互作用的基本粒子)的结构提供了有力的工具。在某种意义上说,引力场也是一种规范场。所以这一理论在物理中的作用非常重要。数学家注意到杨-米尔斯场中的规范势恰是数学家在20世纪30~40年代以来深入研究过的纤维丛上的联络。不仅如此,他们还发现,这一理论中出现的杨-米尔斯方程是一组数学上未曾考虑到的极有意义的非线性偏微分方程。1975年以来数学家对杨-米尔斯方程进行了许多深入的研究,这些研究对于纯粹数学的发展,也起了推动作用。
6、纳卫尔-斯托可(Navier-Stokes)方程
纳卫尔-斯托可(Navier-Stokes)方程也称纳威厄-斯托克斯方程(Navier-Stokes Equations):证明或否定3-维奈维尔-斯托克斯方程解的存在性和光滑性(在合理的边界和初始条件下)。
纳维叶-斯托克斯(Navier-Stokes)方程的存在性与光滑性
起伏的波浪跟随着我们的正在湖中蜿蜒穿梭的小船,湍急的气流跟随着我们的现代喷气式飞机的飞行。数学家和物理学家深信,无论是微风还是湍流,都可以通过理解纳维叶-斯托克斯方程的解,来对它们进行解释和预言。虽然这些方程是19世纪写下的,我们对它们的理解仍然极少。挑战在于对数学理论作出实质性的进展,使我们能解开隐藏在纳维叶-斯托克斯方程中的奥秘。
7、BSD(Birch and Swinnerton-Dyer)猜想
BSD猜想属于数论中的内容,是关于方程的整数和有理数解的问题。
数学家总是被诸如x2+y2=z2那样的代数方程的所有整数解的刻画问题着迷。欧几里德曾经对这一方程给出完全的解答,但是对于更为复杂的方程,这就变得极为困难。事实上,正如马蒂雅谢维奇指出,希尔伯特第十问题是不可解的,即,不存在一般的方法来确定这样的方法是否有一个整数解。当解是一个阿贝尔簇的点时,贝赫和斯维讷通-戴尔猜想认为,有理点的群的大小与一个有关的蔡塔函数z(s)在点s=1附近的性态。特别是,这个有趣的猜想认为,如果z(1)等于0,那么存在无限多个有理点(解),相反,如果z(1)不等于0,那么只存在有限多个这样的点
参考资料:http://baike.baidu.com/view/521722.htm