1、庞加莱猜想 （已证成立） 庞加莱猜想 最早是由法国 数学家 庞加莱 提出的一个猜想，是 克雷数学研究所 悬赏的数学方面七大 千禧年难题 之一。 2006 年 确认由俄罗斯数学家 格里戈里佩雷尔曼 完成最终证明，他也因此在同年获得 菲尔兹奖 ，但并未 现身领奖 12。 基本描述 在 1904 年 发表的一组论文中， 庞加莱 提出以下猜想： 任一 单连通 的、 封闭 的三维 流形 与三维球面 同胚 。 上述简单来说就是：每一个没有破洞的封闭三维物体，都 拓扑等价 于三维的球面。粗浅的比喻即为：如果我们伸缩围绕一个苹果表面的橡皮带，那么我们可以既不扯断它，也不让它离开表面，使它慢慢移动收缩为一个点；
2、另 一方面，如果我们想象同样的橡皮带以适当的方向被伸缩在一个 轮胎面 上，那么不扯断橡皮带或者轮胎面，是没有办法把它不离开表面而又收缩到一点的。我们说，苹果表面是“ 单连通 的”，而轮胎面不是。 该猜想是一个属于 代数拓扑学 领域的具有基本意义的 命题 ，对“庞加莱猜想”的证明及其带 来的后果将会加深数学家对 流形 性质的认识，甚至会对人们用 数学语言 描述 宇宙 空间产生影响。 证明历史 20 世纪 这个问题曾经被搁置了很长时间，直到 1930 年 怀特海 （ J. H. C. Whitehead）首先宣布已经证明然而又收回，才再次引起了人们的兴趣。怀特海提出了一些有趣的三流形实例，其原型现
3、在称为 怀特海流形 。 1950 和 1960 年代，又有许多著名的数学家包括 R H宾（ R. H. Bing）、 沃夫冈哈肯 （ Wolfgang Haken）、 爱德华摩斯 （ Edwin E. Moise）和 Christos Papakyriakopoulos 声称得到了证明，但最终都发现证明存在致命缺陷。 1961年 ，美国数学家 史提芬斯梅尔 采用十分巧妙的方法绕过三、四维的困难情况，证明了五维以上的庞加莱猜想。这段时间对于低维拓扑的发展非常重要。这个猜想逐渐以证明极难而知名，但是证明此猜想的工作增进了对三流形的理解。 1981年 美国数学家 麦克傅利曼 （ Michael Fr
4、eedman）证明了四维猜想，至此广义庞加莱猜想得到了证明。 1982 年， 理查德汉密尔顿 引入了“ 瑞奇流 ”的概念，并以此证明了几种特殊情况下的庞加莱猜想。在此后的几年中，他进一步地发展了此方法，后来被佩雷尔曼的证明所使用。 21 世纪 俄罗斯 数学家 格里戈里佩雷尔曼 在 2002 年 11月和 2003 年 7月之间， 俄罗斯 的数学家 格里戈里佩雷尔曼 在arXiv.org 发表了三篇论文预印本，并声称证明了 几何化猜想 。 在佩雷尔曼之后，先后有 3 组研究者发表论文补全佩雷尔曼给出的证明中缺少的细节。这包括 密歇根大学 的 布鲁斯 克莱纳 和 约翰洛特 ； 哥伦比亚大学 的 约
5、翰摩根 和 麻省理工学院 的 田刚 ；以及 理海大学 的 曹怀东 和 中山大学 的 朱熹平 。据报道3， 2006 年 6月 3日 ， 丘成桐 曾表示曹怀东和朱熹平第一个给出了庞加莱猜想的完全证明 4。 2006 年 8月，第 25 届国际数学家大会授予佩雷尔曼菲尔兹奖，但佩雷尔曼拒绝接受该奖 5。数学界最终确认佩雷尔曼的证明解决了庞加莱猜想。 2010 年 3月 18 日 ，克雷数学研究所对外公布， 俄罗斯 数学家格里戈里佩雷尔曼（俄语： ， 1966年 6 月 13日出生）因为破解庞加莱猜想而荣膺 千禧年大奖 67。 纽约客 专文及相关争议 2006 年 8月 28 日出版的纽约客杂志发表
6、西尔维亚娜莎和大卫格鲁伯的长文 流形的命运 传奇问题以及谁是破解者之争 。该文介绍了佩雷尔曼等人的工作并描画了“一个令人厌恶的丘成桐的形象，暗示他为他的学生曹怀东和他支持的朱熹平的工作宣传了过多的功劳。” 8。此文发表后，引发了很大争议。包括汉密尔顿在内的多名数学家发表声明表 示文章没有正确地反映他们对丘的评价，丘成桐也表示可能采取法律行动。 一名加州理工学院的研究者指出曹、朱论文 4中引理 7.1.2 与克莱纳和洛特 2003年发表的成果 9几乎完全相同。据此，洛特指责曹和朱两人有剽窃的行为。此后，曹怀东和朱熹平在原刊发表纠错声明，确认了此引理是克莱纳和洛特的成果，解释没有指明出处是由于编辑
7、上的差错，并为此向两位原作者致歉。 P/NP问题 P/NP问题 是在 理论信息学 中 计算复杂度理论 领域里至今没有解决的问题，它被“ 克雷数学研究所 ”（ Clay Mathematics Institute，简称 CMI）在 千禧年大奖难题 中收录。 P/NP 问题中包含了 复杂度类 P与 NP 的关系。 1971 年 史提芬古克（ Stephen A. Cook）和 Leonid Levin 相对独 立的提出了下面的问题，即是否两个复杂度类 P和 NP 是恒等的（ P=NP?）。 P 和 NP 复杂度类 P 即为所有可以由一个 确定型图灵机 在多项式表达的时间内解决的问题；类 NP由所有
8、可以在多项式时间内验证解是否正确的决定问题组成，或者等效的说，那些解可以在 非确定型图灵 机 上在 多项式时间 内找出的问题的集合。很可能， 计算理论 最大的未解决问题就是关于这两类的关系的： P 和 NP 相等吗？ 在 2002 年对于 100 研究者的调查， 61 人相信答案是否定的， 9个相信答案是肯定的， 22 个不确定，而 8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。 1 对于正确的解答，有一个 $1,000,000 美元的奖励 。 NP-完全 问题（或者叫 NPC）的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在 NP 中最不像在 P 中的（确切定义细
9、节请参看 NP-完全 理论）。计算机科学家 现在相信 P, NP，和 NPC 类之间的关系如图中所示，其中 P和 NPC类不交。 假设 P NP的复杂度类的图解。如 P = NP 则三个类相同。 简单来说， P = NP 问题问道：如果是不是问题的正面答案可以很快 验证 ，其答案是否也可以很快 计算 ？这里有一个给你找点这个问题的感觉的例子。给定一个大数 Y，我们可以问 Y是否是 复合数 。例如，我们可能问 53308290611 是否有非平凡的 因子 。答案是肯定的，虽然手工找出一个因子很麻烦。从另一个方面讲，如果有人声称答案是 “对，因为 224737 可以整除 53308290611“，
10、则我们可以很快用一个除法来验证。验证一个数是除数比找出一个明显除数来简单得多。用于验证一个正面答 案所需的信息也称为 证明 。所以我们的结论是，给定正确的证明，问题的正面答案可以很快地（也就是，在多项式时间内）验证，而这就是这个问题属于 NP的原因。虽然这个特定的问题，最近被证明为也在 P 类中（参看 下面的 关于 “质数在 P中 “的参考），这一点也不明显，而且有很多类似的问题相信不属于类 P。 像上面这样，把问题限制到“是不是”问题并没有改变原问题（即没有降低难度）；即使我们允许更复杂的答案，最后的问题（是否 FP = FNP）是等价的。 学术定义 更正式一些，一个 决定问题 是一个取一些
11、 字符串 为输入并要求输出为是或否的问题。若有一个 算法 （譬如 图灵机 ，或一个 LISP 或 Pascal 的程序并有无限的内存）能够在最多 nk步内对一个串长度为 n的输入给出正确答案，其中 k是某 个不依赖于输入串的常数，则我们称该问题可以在 多项式时间 内解决，并且将它置入类P。直观的讲，我们将 P 中的问题视为可以较快解决的问题。 现在假设有一个算法 A(w,C)取两个参数，一个串 w，也就是我们的决定问题的输入串，而另一个串 C是“建议证明”，并且使得 A在最多 nk步之内产生“是否”答案（其中 n 是 w 的长度而 k 不依赖于 w）。进一步假设 w 是一个答案为“是”的例子，
12、当且仅当，存在 C使得 A(w,C)返回“是”。 则我们称这个问题可以在 非决定性多项式时间 内解决，且将它放入 NP类。我们把算法 A作为一个所建议的证明的检验 器，它运行足够快。（注意缩写 NP 代表“ Non-deterministic（非确定性） Polynomial（多项式）”而 不是 代表“ Non-Polynomial（非多项式）。） NP 完全 要解决 P = NP 问题， NP完全 的概念非常有用。不严格的讲， NP完全问题是 NP类中“最难”的问题，也就是说它们是最可能不属于 P 类的。这是因为 任何 NP中的问题可以在多项式时间内变 换成为任何特定 NP 完全问题的一个特
13、例。例如，旅行推销员问题 的判定问题版本是 NP 完全的。所以 NP 中的 任何 问题的 任何 特例可以在多项式时间内机械地转换成旅行商问题的一个特例。 所以若旅行商问题被证明为在 P 内，则 P = NP！旅行商问题是很多这样的 NP 完全的问题之一。若任何一 个 NP 完全的问题在 P 内，则可以推出 P = NP。不幸的是，很多重要的问题被证明为 NP 完全，但没有一个有已知快速的算法。 更难的问题 虽然是否 P=NP 还是未知的，在 P 之外的问题是已经知道存在的。寻找 国际象棋或 围棋 最佳走法（在 n 乘 n 棋盘上）是 指数时间完全 的。因为可以证明 P EXPTIME（指数时间
14、），这些问题位于 P 之外，所以需要比多项式时间更多的时间。判定 Presburger 算术 中的命题是否为真的问题更加困难。 Fischer 和 Rabin于 1974年 证明每个决定 Presburger命题的真伪性的算法有最少 22cn的运行时间，c为某个常数。这里， n 是 Presburger 命题的长度。因此，该命题已知需要比指数时间更多的运行时间。不可判定问题是更加困难的，例如 停机问题 。它们无法在任何给定时间内解决。 P 真的容易处理吗？ 上面所有的讨论，假设了 P 表示“容易”而“不在 P 中”表示“困难”。这是一个在复杂度理论中常见而且有一定准确性的假设，它在实践中却不总
15、是真的，原因包括如下几点： 它忽略了常数因子。一个需要 101000n时间的问题是属于 P 的（它是线性时间的），但是事实上完全无法处理。一个需要 10-100002n时间的问题不是在P 中的（它是指数时间的），但是对于 n取值直到几千时还 是很容易处理的。 它忽略了指数的大小。一个时间复杂度 n1000属于 P，但是很难对付。已经证明在 P 中存在需要任意大的指数的问题（参看 时间等级定理 ）。一个时间复杂度 2n/1000的问题不属于 P，但对与 n 直到几 千还是容易应对的。 它只考虑了最坏情况的复杂度。可能现实世界中的有些问题在多数时候可以在时间 n 中解决，但是很偶尔你会看到需要时间
16、 2n的特例。这个问题可能有一个多项式的平均时间，但最坏情况是指数式的，所以该问题不属于 P。 它只考虑确定性解。可能有一个问题你可以很快解决如果你可以接受出现一点误差的可能，但是确保正确的答案会难得多。这个问题不会属于 P，虽然事实上它可以很快求解。这实际上是解决属于 NP 而还不知道是否属于 P 的问题的一个办法（参看 RP， BPP）。 新的诸如 量子计算机 这样的计算模型，可能可以快速的解决一些尚未知道是否属于 P 的问题；但是，没有一个它们已知能够解决的问题是 NP 完全的。不过，必须注意到 P 和 NP 问题的 定义 是采用像图灵机这样的经典计算模型的术语表述的。所以，即使一个量子
17、计算机算法被发现能够有效的解决一个 NP 完全问题，我们只是有了一个快速解决困难问题的实际方法，而不是数学类 P 和 NP相等的证明。 计算机科学家为什么认为 P NP？ 多数计算机科学家相信 P NP。该信念的一个关键原因是经过数十年对这些问题的研究，没有人能够发现一个 NP完全问题的多项式时间算法。而且，人们早在NP完全的概念出现前就开始寻求这些算法了 （ Karp 的 21 个 NP完全问题 ，在最早发现的一批中，有所有著名的已经存在的问题）。进一步地， P = NP 这样的结果会导致很多惊人的结果，那些结果现在被相信是不成立的，例如 NP = 反 NP和 P = PH。 也有这样论证的
18、：问题较难求解（ NP）但容易验证（ P），这和我们日常经验是相符的。 从另一方面讲，某些研究者认为我们过于相信 P NP，而应该也去寻找 P = NP的 证明。例如， 2002 年中有这样的声明： 2 倾向 P NP 的主要论据是在穷尽搜索的领域完全没有本质进展。也就是说，以我的观点，一个很弱的论据。算法的空间是很大的，而我们只是在开始探索的起点。 . . . 费马最后定理 的解决也显示非常简单的 sic问题可能只有用非常深刻的理论才能解决。 摩西瓦迪 （ Moshe Vardi）， 莱斯大学 过分依赖某种投机的猜测不是规划研究的一个好的导引。我们必须总是尝试每个问题的两个方向。偏见可能导致
19、著名的数学家无法解决答案和他们的预计相反的著名问题，虽然他们发展了所有所需的方法。 Anil Nerode, 康奈尔大学 关于证明的难度的结果 虽然百万美元的奖金和投入巨大却没有实质性结果的大量研究足以显示该问题是困难的，但是还有一些形式化的结果证明为什么该问题可能很难解决。 最常被引用的结果之一是设计 神谕 。假想你有一个魔法机器可以解决单个问题，例如判定一个给定的数是否为质数，可以瞬间解决这个问题。 我们的新问题是，若我们被允许任意利用这个机器，是否存在我们可以在多项式时间内验证但无法在多项式时间内解决的问题？结果是，依赖于机器能解决的问题， P = NP 和 P NP二者都可以证明。这个
20、结论带来的后果是，任何可以通过修改来证明该机器的存在性的结果不能解决问题。不幸的是，几乎所有经典的方法和大部分已知的方法可以这样修改（我们称它们在 相对化 ）。 如果这还不算太糟的话， 1993 年 Razborov 和 Rudich 证明的一个结果表明，给定一个特定的可信的假设，在某种意义下“自然”的证明不能解决 P = NP 问题。3 这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类定理得到证明，该定理的可能证明方法有越来越多的陷阱要规避。 这实际上也是为什么 NP 完全问题有用的原因：若对于 NP 完全问题存在有一个多项式时间算法，或者没有一个这样的算法，这将能用一种相信不被上
21、述结果排除在外的方法来解决 P = NP 问题。 多项式时间算法 没人知道多项式时间算法对于 NP完全问题是否存在。但是如果这样的算 法存在，我们已经知道其中的一些了！例如，下面的算法正确的接受了一个 NP 完全语言，但是没人知道通常它需要多久运行。它是一个多项式时间算法当且仅当 P = NP。 / 接受 NP 完全语言的一个算法 子集和 。 / / 这是一个多项式时间算法当且仅当 P=NP。 / / “多项式时间”表示它在多项式时间内返回“是”，若 / 结果是“是”，否则永远运行。 / / 输入： S = 一个自然数的有限集 / 输出： “是 “如果某个 S 的子集加起来等于 0。 / 否则
22、，它永远运行没有输出。 / 注意 : “程序数 P“是你将一个整数 P写为二进制，然后 / 将位串考虑为一个程序。 / 每个可能的程序都可以这样产生， / 虽然多数什么也不做因为有语法错误。 / FOR N = 1.infinity FOR P = 1.N 以 S为输入运行程序数 P N 步 IF 程序输出一个不同的整数的列表 AND 所有整数都在 S 中 AND 整数的和为 0 THEN OUTPUT “是 “并 停机 若 P = NP，则这是 一个接受一个 NP 完全语言的多项式时间算法。“接受”表示它在多项式时间内给出“是”的答案，但允许在答案是“否”的时候永远运行。 可能我们想要“解决
23、”子集和问题，而不是仅仅“接受”子集和语言。这表示我们想要它总是停机并返回一个“是”或“否”的答案。是否存在任何可能在多项式时间内解决这个问题的算法？没有人知道。但是如果这样的算法存在，那么我们已经知道其中的一些了！只要将上面的算法中的 IF 语句替换成下面的语句： IF 程序输出一个完整的数学证明 AND 证明的每一步合 法 AND 结论是 S 确实有（或者没有）一个和为 0的子集 THEN OUTPUT “是 “（或者 “不是 “如果那被证明了）并停机 逻辑表述 P=NP 问题可以用逻辑命题的特定类的可表达性的术语来重新表述。所有 P中的语言可以用 一阶逻辑 加上 最小不动点 操作（实际上
24、，这允许了递归函数的定义）来表达。类似地， NP 是可以用存在性 二阶逻辑 来表达 也就是，在关系、函数、和子集上排除了 全称量词 的二阶逻辑。 多项式等级 ， PH中的语言对应与所有的二阶逻辑 。这样，“ P 是 NP 的真子集吗”这样的问题可以表述为“是否存在性二阶逻辑能够表达带最小不动点操作的一阶逻辑的所不能表达的语言？” 霍奇猜想 霍奇猜想 是 代数几何 的一个重大的悬而未决的问题。它是关于 非奇异 复 代数簇 的代数拓扑 和它由定义子簇的多项式方程所表述的几何的关联的猜想。它在 霍奇 的著述的一个结果中出现，他在 1930 至 1940 年间通过包含额外的结构丰富了 德拉姆上同调 的
25、表述，这种结构出现于代数簇的情况（但不仅限于这种情况）。 黎曼猜想 黎曼猜想 由 德国 数学家 波恩哈德黎曼 于 1859 年提 出。它是数学中一个重要而又著名的 未解决的问题 。多年来它吸引了许多出色的数学家为之绞尽脑汁。 黎曼猜想 ： 黎曼函数 ， 。 非平凡零点 (在此情况下是指 s 不为 -2、 -4、 -6等点的值 )的实数部份是。 未解决的数学问题 : 黎曼 函数 的每个非平凡零点的实部是否同为 ？ 黎曼猜想（ RH）是关于 黎曼函数 (s)的零点分布的猜想。 黎曼函数 在任何复数 s 1上有定义。它在负偶数上也有零点（例如，当 s = 2, s = 4, s = 6, .）。这些
26、零点是“平凡零点”。黎曼猜想关心的是非平凡零点。 黎曼猜想提出： 黎曼函数 非平凡零点的实数部份是 即所有的非平凡零点都应该位于直线 + ti（“临界线”）上。 t为一实数，而i为虚数的基本单位。沿临界线的黎曼函数有时通过 Z-函数 进行研究。它的实零点对应于函数在临界线上的零点。 素数 在 自然数 中的分布问题在纯粹数学和应用数学上都很重要。 素数 在自然数中的分布并没有简单的规律。 黎曼 （ 1826-1866）发现素数出现的频率与 黎曼函数 紧密相关。 1901 年 Helge von Koch 指出，黎曼猜想与强条件的 素数定理等价。现在已经验证了最初的 1,500,000,000 个
27、素数对这个定理都成立。但是是否所有的解对此定理都成立，至今尚无人给出证明。 黎曼猜想所以被认为是当代数学中一个重要的问题，主要是因为很多深入和重要的数学和物理结果都能在它成立的大前提下被证明。大部份数学家也相信黎曼猜想是正确的（ 约翰恩瑟李特尔伍德 与 塞尔伯格 曾提出怀疑。塞尔伯格于晚年部分改变了他的怀疑立场。在 1989 年的一篇论文中，他猜测黎曼猜想对更广泛的一类函数也应当成立。） 克雷数学研究所 设立了 $1,000,000 美元的奖金给予第一个得出正确证明的人。 编辑 历史 黎曼函数 在临界线 Re(s) = 1/2 上的实部（红色）和虚部（蓝色）。我们可以看到最起初的几个非平凡零点
28、就位于 Im(s) = 14.135, 21.022 和 25.011上。 黎曼函数 实部与虚部的数值比较图，也就是 Re( (s) vs. Im( (s)，沿着临界线 s = it + 1/2， t 由 0 到 34 黎曼 1859 年在他的论文 ber die Anzahl der Primzahlen unter einer gegebenen Gre中提及了这个著名的猜想，但它并非该论文的中心目的，他也没有试图给出证明。黎曼知道函数的不平凡零点对称地分布在直线 s = + it上，以及他知道它所有的不平凡零点一定位于区域 0 Re(s) 1 中。 1896 年， 雅克阿达马 和 Cha
29、rles Jean de la Valle-Poussin 分别独立地证明了在直线 Re(s) = 1 上没有零点。连同了黎曼对于不非凡零点已经证明了的其他特性，这显示了所有不平凡零点一定处于区域 0 Re(s) 1 上。这是 素数定理 第一个完整证明中很关键的一步。 1900 年， 大卫希尔伯特 将黎曼猜想包括在他著名的 23 条问题 中，黎曼猜想与哥德巴赫猜想 一起组成了希尔伯特名单上第 8 号问题。当被问及若他一觉醒来已是五百年后他将做什么时， 希尔伯特 有名地说过他的第一个问题将是黎曼猜想有否被证明。 (Derbyshire 2003:197; Sabbagh 2003:69; Bollobas 1986:16).黎曼猜想是 希尔伯特问题 中唯一一个被收入 克雷数学研究所 的 千禧年大奖数学难题 的。 1914 年， 高德菲哈罗德哈代 证明了有无限个零点在直线 Re(s) = 上。然而仍然有可能有无限个不平凡零点位于其它地方（而且有可能是最主要的零点）。
