这页就说点被认为将使世界天翻地覆的计算机科学的第一难题吧

即最近出版我们琼州大学论文的这里的杂志Monatshefte fur Mathematik1931年出版并已成为20世紀《数学》世界最重要的真理的论文,又再令人意想不到地-酝酿出被认为将使21世纪世界天翻地覆《计算机》世界第一问题-PNP问题即这个问题是Godel即哥德尔在他的上面论文的基础上于1956年写给John von Neumann的信中最先提出的。此论文作者Godel一生论著不多,著名的仅仅是1931的上面杂志的论文-这里最后见他仍成为20世纪世界第一数学家(在网上输入Godel德尔和爱因斯坦平起平坐的

其后,1993年起开始颁发以Godel命名的计算机理论界成果最高奖-Godel。这很容易让人误认为是因提出上面问题才得以他的名义命此奖。此授奖名册网也说以他命名是因为提出这问题。但其实,试想一个如此重要的世界顶级奖怎么可能由提出一个问题的人名命奖呢?虽也有此原因,但主要是由下面历史决定(也就是由发表我们琼州大学论文的这个网上Monatshefte fur Mathematik杂志1931年的Godel论文决定,其实有这篇论文,才酝酿出上面PNP问题):

问题的起源是,20世纪之初,希尔伯特提出可判定性问题,因而引起人们的关注。可判定性问题大体相当于询问,是否存在一个算法,对任意给定命题都能判定它是否可以根据一组公理证明。解决此问题的开路先锋是这里最后一行说的美国《时代》杂志曾评选出的20世纪全球100个最伟大数学家中排在第一Kurt Godel(库尔特·哥德尔)发表在这里我们琼州大学也发表的Monatshefte fur Mathematik杂志1931年的不完备性定理工作。算法的直观概念就是一系列合起来能够求解某问题的简单步骤。从哥德尔一生发表论著不多,足见好论文一篇足唉!

巧的是,我们琼州大学在上面杂志Monatshefte fur Mathematik发表的论文正是“泛连通图性的”。而泛连通图问题是所有HC相关的NP完全问题中结构最为复杂的。在如此长期的困惑下,现在谁也不知道是否最危险的地方最安全,最复杂的NP完全问题最能突出更多P问题实质,因而若能证明泛连通图问题ÎP,就是证明NP=P,从而使世界天翻地覆

这里有一个关于上面Godel的资料:它是1993年诺贝尔奖得主Juris Hartmanis写的“Gödel, von Neumann, and the P =? NP problem”,Bulletin European Assoc. Theor. Computer Science, 38, 1989, 101-107

尽管世界各地的一流数学家已经求解哈密顿圈几十年了,但人们至今依然不知道,对于一般的哈密顿圈,如何才能得出远远优于简单暴力枚举检验的通用解法。很有可能根本就没有一种高效解法能保证该问题的所有具体题目。

我们也许连解法的影子都没有看到。但这并不意味着数学家至今的研究都一无所获。事实上,这道问题带来了许多美妙而深刻的结论和猜想。如已解决了八万多个城市的难题,他们的解法使使这题的最优线路经过计算脱颖而出,而若是对数目异常庞大的所有路线逐一检验,需要用顶尖计算机工作站连续运转136年。

关于P=NP,下面记述某些相关专家的看法:聪明过人Richard Karp在我们1972年的论文(Reducibility among combinatorial problems)中给出了一些定理,它们有力地暗示(尽管不是证明):最小哈密顿圈像许多别的问题一样,也将是一道永恒的难题

多次获得科幻艺术界的诺贝尔奖的Charles Stross的科幻小说《抗体》(Antibodies)说,有人找到了旅行商问题的高效算法,结果就像世界末日一样,种种事件接踵而来。即人工智能程序突然效率大增,从而推翻了有生命的主人并取而代之(确实,这TSP真相大白件事一旦发生-即找到高效算法,必然会让世界天翻地覆。但是,现在看来,好的对人类有利的方面要远远大于不利的方面。因此,TSP真相大白的那一刻不会宣告所谓的世界末日。正如Lance Fortnow在一篇综述中写道很多人只关注问题的负面,认为P=NP会让公开密钥加密技术完全失效。确实如此,但是P=NP的益处更大,足以使整个互联网变成历史上微不足道的脚注。“P=NP意味着我们能快速地了解一切,揭开世界上所有事物的神秘面纱,洞察宇宙的本质。我们所了解的社会将会发生剧变,医学、科学、娱乐和人类社会一切任务的自动化程度都将发生质的飞跃”,“即我们将能更好地利用可用的资源。科学界、经济界、工业界将出现更加强大的工具和方法,重大突破源源不断。接下来的的数年内,诺贝尔奖委员会将忙得不可开交。那是一个如花似锦的世界(这Lance Fortnow虽算不得大师但也是一线专家如他是ACM Transaction on Computation Theory创刊主编、ACM SIGACT前主席、IEEE Conference on Computational Complexity主席等,且都是计算复杂性方面的。附一个信息:最近这Lance Fortnow的导师即麻省理工学院SS院长Michael Sipser院士在对哈佛博士William Gasarch的一个调查问卷中回答大约在2037年左右能解决PNP问题Michael Sipser并说解决这问题的方法技术只有靠我们的组合数学--而没有说要靠其它别的学科的方法)。还有计算机科学大牛Avi Widgerson也曾表示复杂性理论与人类知识限界之间或许存在关联。确实,如果能证明P=NP,那么人类将大步跨进新时代,拥有能够建模并利解世界的高效计算工具。有此观点也许还因为NP完全问题已有近万个之多,而难道就没有一个是多项式时间复杂度的吗?当然,也可能非P=NP,也就是部分问题不可能用自动化的方法迅速解决,不过知道哪些工具不好用也有助于人们找到更好用的工具(可参考一些综述或杂论:如NP完全问题的开创者Cook.的“The P versus NP Problem”;美国三院院士Papadimitriou撰写的NP完全问题的回顾综述;新晋院士Avi Widgerson的“P, NP and Mathematics - a computational complexity perspective”;上面Lance FortnowSteven Homer合写的“A Short History of Computational Complexity”等)

这个问题可见美国克雷研究所发布的奖励百万美元的千禧年难题的公报更多相关知识,这个网;这里是一个计算机科学理论与图论

 

附:上面和琼州大学一同发表在Monatshefte fur Mathematik杂志上Kurt Gödel1931年的论文已是众所周知在逻辑、数学、人工智能等学科都具有非常重要的地位;然而,它更在计算机上具有先驱的作用:如在网上普遍见到权威的说法是计算机之父Alan Turing,“who set out the idea in his seminal 1936 paper, On Computable Numbers. Turing reformulated Kurt Gödel's 1931 results on the limits of proof and computation, replacing Gödel's universal arithmetic-based formal language with the formal and simple hypothetical devices that became known as Turing machines”。而关于Alan Turing的这论文,另一计算机之父John Von Neumannacknowledged that the central concept of the modern computer was due to this paper”和“von Neumann ... firmly emphasized to me, and to others I am sure, that the fundamental conception is owing to Turing—insofar as not anticipated by Babbage, Lovelace and others”。

再说与组合数学有关的一件有趣的事,即比尔·盖茨在成为全球首富之前在杂志发表的第一作者论文只有一篇,就是这里这篇在我们的《离散数学》杂志发表的组合数学论文(就是琼州大学报道说到的美国三院院士Papadimitriou和他的学生比尔·盖茨合作的这篇或见这里。关于离和组的关系,南开大学校长陈永川院士说离散数学又称组合数学。关于组合数学或离散数学的作用,比尔·盖茨说“数学与电脑程序设计有着非常直接的关系。这一点也许在我心目中要远远胜过别人”)