Lost in Math?

By Moshe Y. Vardi
Communications of the ACM, March 2019, Vol. 62 No. 3, Page 7
10.1145/3306448
Translated by Xiaohu Zhu

当我10岁的时候，我的数学老师开了一个数学俱乐部。它不够流行以致持续时间可以超过几周，但这足以让我了解矩阵和行列式。当我回到家时，妈妈问我俱乐部是怎么样。 “很漂亮，” 我回答。 “你的意思是，’有趣’？” 她问道。 “不，”我说，“美丽！” 虽然有些人发现数学令人困惑，但其他人却觉得它优雅而美丽。数学家保罗·埃尔德斯经常提到“天书”，其中上帝保留了每个数学定理的最美丽的证明。哲学家伯特兰·罗素（Bertrand Russell）曾说：“数学，正确地看待，不仅拥有真理，而且拥有至高无上的美。”美丽可以引人注目；如此美丽的东西一定是真的！

但最近数学之美的诱人力量受到了批评。理论物理学家 Sabine Hossenfelder 在今年早些时候出版的“Lost in Math”中断言，数学上的优雅导致物理学误入歧途。具体而言，她认为物理学的几个分支，包括弦论和量子引力，在没有实验数据证实或反驳这些理论的情况下已经将数学之美作为真理标准。她认为，理论物理学界正在成为集体思维和认知偏见的牺牲品，受到数学之美的诱惑。大约 10 年前，在 2008 年金融危机之后，诺贝尔经济学奖获得者保罗·克鲁格曼在经济学和数学方面提出了同样的观点，题目是“经济学家如何会出现这样的错误？”他的主要答案是：误将数学之美看作真理。 “正如我所看到的那样，”克鲁格曼写道，“经济学界误入歧途，因为经济学家作为一个群体，误认为披着令人印象深刻的数学外衣的美丽，为真理。”

因此，物理学和经济学都可以说在数学上已经迷失了。那计算机科学怎么样？具体来说，理论计算机科学（TCS）呢？ TCS 肯定拥有数学之美。很久以前，作为一名研究生，数学之美将我指引到TCS领域，并继续引导我的研究多年。我发现计算复杂性理论（或简称复杂性理论）及其定理（例如，时间层次和空间层次定理）及其开放问题（例如，P vs NP），令人难以忘怀。美丽，的确是的；但真相呢？

物理理论描述了物理世界，而他们的“真理”则指的是他们描述这个世界的忠诚度。经济学理论描述了经济系统，但是通过它们的“真理”，我们不仅指它们描述这种系统的忠诚度，而且还指它们为商业人士和政策制定者提供的指导的质量。我认为计算复杂性理论在这方面类似于经济理论。它不仅应该提供一个理论框架，我们可以在其中研究算法的性能，但它也应该为使用算法的算法设计者和系统开发人员提供合理的指导。那么从这个角度看计算复杂性理论的理论有多好？

很清楚在特定问题实例 I 上测量特定算法 A 的性能意味着什么。但是复杂性理论旨在描述 A 在所有问题实例的空间上的性能，并且它通过从各个问题实例中抽象出来而实现这一点。 我们执行此抽象的典型方法是考虑长度为 n 的所有问题实例，并要求算法性能的上限和下限（通常在时间和内存利用方面）作为n的函数。这种方法被称为最坏情况方法，因为它专注于每个长度 n 最具挑战性的问题实例。如果我们可以证明的上界是缓慢增长函数之一，例如 cn log n，对于一个小常数 c ，那么我们可以保证在所有问题实例上都有良好的性能。但是，一般来说，大多数上界和下界都没那么有用。例如，指数级下界只是表示某些问题实例很难，但没有说明此类实例的实际意义。

在之前的专栏中，我在特定环境中讨论了理论与实践之间的这种差距。正如我所指出的，程序终止在理论上可能是无法解决的，但在实践中是可以解决的 [a]，但布尔可满足性在理论上可能是难以处理的，但在实践中是易处理的 [b]。在这两种情况下，最坏情况的方法过于悲观并且告诉我们太少关于实践中的算法性能。美不一定需要真相。超越最坏情况的复杂性研究是复杂性理论中的关键挑战，也是当前许多研究工作的主题。 （参见Tim Roughgarden的评论文章，第88页）。