厄巴纳算法

[美]Lance Fortnow 

2017.10.26   课堂展示材料

2016年，捷克数学家米莱娜·帕维尔用邮件转发了一个她认为理论上能有效解决NP问题的算法。计算机科学和数学界经过仔细验证，一致认为米莱娜所言不虚，算法确实解决了伟大的P/NP问题。米莱娜将算法发表成论文，文章本身的名字很低调，叫做“论一个库克没有解决的问题”（On an Open Problem of Cook），而《纽约时报》介绍文章的标题更为直白，恰如其分地表明了它的价值：“P=NP”。

2018年，米莱娜成为第一个获得数学领域最高荣誉（菲尔兹奖）的女性。一年后克雷数学研究所奖给米莱娜一张价值100万美元的支票。她成为继格里高利·佩雷尔曼之后第二个成功解决千禧年数学难题的人。不像佩雷尔曼，她高兴地收下了奖金，并将其中一部分（数额未知）捐给了故乡布拉格的大学作为奖学金。虽然米莱娜的算法在理论上是一个突破，但因为实际执行时间过长而缺乏实用价值。2017年，俄罗斯计算机科学家明斯克·波洛夫采用一种巧妙的方法改良了米莱娜的算法，从而大幅改进了算法的执行效率，然而还是不够实用。

一年后在中国，清华大学的一群本科生仔细优化了明斯克的代码，在当时世界上最快的超级计算机上运行它。他们在几天之内就解决了较大规模的团问题和其他几个常见的NP问题。清华大学开始与波音、戴姆勒-奔驰等工业巨头签约，帮助这些公司解决一些棘手的优化问题。他们帮助波音为新797客机设计出了更好的机翼，使得客机能直接从伦敦飞到悉尼。

史蒂夫·弗兰克是伊利诺伊大学的博士生，此时在清华做一学期的访问学者，他有幸参与了项目的研究工作。回到伊利诺伊州的厄巴纳后，他向导师诉苦，无论他们如何优化，还是要花几天时间才能解决一个中等规模的NP问题。“如果你遇到灯神，它能满足你一个愿望，你会许什么愿？”导师说。

“不知道。”史蒂夫回答。

“让它给你一个能满足你所有愿望的灯神！”

史蒂夫脑中一亮。他知道一定存在一个能更好解决团问题的算法，而他自己想不出这个算法。但是他遇到了灯神——清华的代码，他可以用很快的速度搜索指数级数量的可能算法。所以他基于清华的例程写了一个搜索更好的NP问题算法的程序。他获准可以使用位于伊利诺伊大学的国家超级计算应用中心（NCSA）的计算资源。经过几周的计算，他的工作初见成效。他找到了一个比清华的算法性能高5%的算法。这一结果发篇论文绰绰有余，但不会产生轰动效应。

他的导师淡淡地说：“用新算法再试一次。”

于是史蒂夫用他的新算法找到了一个更快的解决NP问题的算法。几周后他获得了20%的性能提升。

但他的导师还不满意：“再试一次。”

史蒂夫这样回答：“我为什么不编个程序让计算机自动使用找到的算法来查找更好的算法呢？”

导师的目光变得异样起来，仿佛在说你终于开窍了，又仿佛在说，这么明显的事你怎么现在才想到。

史蒂夫回到办公室，开始写一个算法，让计算机能自动利用搜索到的更快的算法去查找比当前算法更快的算法，这样一直找下去，直到性能无法提升为止。史蒂夫的一个同事问他是否担心天网效应。

“天网是啥？”“当计算机变得足够聪明，有了自我意识，它就会接管世界，就像《终结者》系列电影里的超级计算机‘天网’一样。”

“不，只是计算机代码而已，不用担心。”

史蒂夫写好了代码，最后一次在NCSA的超级计算机上运行它。随着迭代次数的增加，由计算机自动生成的求解NP问题的算法性能变得越来越好，最后在停止时，生成了一个有4200万行机器码的让人费解的程序。它求解NP问题的速度，那是相当快。（顺便说一句，计算机依然没有自我意识。）某高校出版社将这个算法自豪地称为“厄巴纳算法”，后来这个名字被保留了下来。

伊利诺伊大学的数学家们开始率先使用厄巴纳算法，用它来证明剩下的千禧年数学难题。证明过程是计算机生成的，复杂到人类几乎无法理解。克雷数学研究所很快发表声明，不再接受基于米莱娜·帕维尔发现的百万美元算法衍生出来的任何算法的数学证明。

许多试图以许可证和买断方式获得厄巴纳算法的公司都陷入了诉讼泥潭，因为与算法有关的各方——资助米莱娜研究的捷克政府、史蒂夫·弗兰克、史蒂夫的导师以及NCSA，都主张自己对厄巴纳算法的所有权。

世界贸易组织在认识到该算法的重大意义后，要求公开厄巴纳算法，供全人类共同享用，相关各方将得到合理的补偿，并成立专门委员会落实。2019年10月23日，厄巴纳算法对所有人公开了。

从此，世界发生了一系列戏剧性的变化……

《数说》，说更有意思的数学