ACM通信
部门
迷失在数学中?
当我10岁的时候，我的数学老师成立了一个数学俱乐部。这门课还没普及到能持续几个星期，但已经足够让我学习矩阵和行列式了。当我回到家，妈妈问我俱乐部怎么样。“很漂亮。”我回答。“你是说‘有趣’吗?”她问道。“不，”我说，“太美了!”有些人觉得数学令人困惑，而另一些人则觉得数学优雅而美丽。数学家保罗·厄兹(Paul Erds)经常提到“圣经”，在这本书中，上帝保存了每个数学定理的最漂亮的证明。哲学家伯特兰·罗素说过:“正确地看待数学，它不仅拥有真理，而且拥有至高的美。”美可以是引人注目的; something so beautiful must be true!
但是数学之美的诱惑力量最近受到了批评。在迷失在数学在书中，理论物理学家萨宾·霍森菲尔德(Sabine Hossenfelder)断言，数学的优雅使物理学误入歧途。具体来说，她认为物理学的几个分支，包括弦理论和量子引力，在缺乏实验数据来证实或反驳这些理论的情况下，已经开始将数学之美视为真理的标准。她认为，理论物理学界正在被数学之美所诱惑，成为群体思维和认知偏见的受害者。大约10年前，在2008年金融危机之后，诺贝尔经济学奖得主保罗·克鲁格曼(Paul Krugman)在一篇颇具影响力的文章《经济学家是如何错得这么离谱的?》(How Did Economists Get It So Wrong?)中，就经济学和数学提出了同样的观点。他的主要回答是:将数学之美误认为真理。“在我看来，”克鲁格曼写道，“经济学专业之所以误入歧途，是因为经济学家作为一个群体，把披着令人印象深刻的数学外衣的美误认为了真理。”
因此，可以说，物理学和经济学都被数学淹没了。计算机科学呢?具体来说，理论计算机科学(TCS)怎么样?TCS无疑拥有数学之美。很久以前，作为一名研究生，数学之美吸引了我，并继续领导我的研究多年。我发现了计算复杂性理论(或简称复杂性理论)，以及它的定理(例如，时间层次和空间层次定理)和它的开放问题(例如，PvsNP)，美丽得让人难以忘怀。美,是的,但真相呢?
物理理论描述的是物质世界，我们所说的“真理”指的是它们描述这个世界的忠实度。经济理论描述的是经济体系，但我们所说的“真理”，不仅指它们描述这种体系时的忠实程度，还指它们为商界人士和政策制定者提供的指导的质量。我认为复杂性理论在这方面与经济学理论相似。它不仅应该提供一个理论框架，我们可以在其中研究算法的性能，而且还应该为算法设计者和使用算法的系统开发人员提供良好的指导。那么从这个角度来看，复杂性理论有多好呢?
衡量特定算法的性能意味着什么，这是很清楚的一个在一个特定的问题实例上我。但复杂性理论旨在描述一个在空间上所有问题实例，它通过从单个问题实例中抽象出来来做到这一点。我们进行这种抽象的典型方法是考虑所有长度的问题实例n，并要求算法性能的上下限(通常是时间和内存利用率)作为函数n。这种方法被称为最坏的方法，因为它集中在每个长度中最具挑战性的问题实例n。例如，如果我们能证明的上界是一个慢增长函数，Cn log n，对于一个小常数c，那么我们就有了良好性能的保证所有问题实例。但是，一般来说，大多数的上界和下界都没有那么有用。例如，指数下界只是说明一些问题实例很难，但并没有说明这些实例的实际意义。
在之前的专栏文章中，我讨论过理论和实践之间的差距。正如我所指出的，程序终止在理论上可能无法解决，但在实践中是可以解决的，一个而布尔可满足性在理论上可能难以处理，但在实践中可以处理。b在这两种情况下，最坏情况的方法都过于悲观，并且在实践中告诉我们的算法性能太少。美并不一定意味着真。超越最坏情况的复杂性是复杂性理论的一个关键挑战，也是当前许多研究的主题。(见Tim Roughgarden的评论文章，第88页)。
脚注
一个。//www.eqigeno.com/magazines/2011/7/109895-solving-the-unsolvable/fulltext
b。//www.eqigeno.com/magazines/2014/3/172516-boolean-satisfiability/fulltext
数字图书馆是由计算机协会出版的。版权所有©2019 ACM, Inc.
评论
蒂莫西·戴维斯
代码之美是否与数学之美不同?
数学语句$x=A^{-1}b$很漂亮，但它不是解决线性系统的糟糕方法。在大多数情况下，它在密集情况下是不准确的，在稀疏情况下是O(n^3)时间，而一个好的稀疏求解器在同一个矩阵上可以花费O(n)时间。所以我想说，虽然x=inv(A)*b在MATLAB中看起来很漂亮，但实际上它真的很丑。MATLAB表达式x=A\b真的很漂亮。
我称这种情况为“MATLAB inv滥用”，尽管MATLAB代码分析器对此提出了警告，但这种情况还是非常普遍。根据我的统计，MATLAB Central所有用户的贡献中有6%使用inv(A)，几乎所有的都是'inv滥用'，我敢大胆猜测，这些代码的作者被美丽的数学语句$x=A^{-1}b$所误导，写了丑陋的'x=inv(A)*b'。
然而代码的美感是很重要的。我会说，当代码写得很好，文档也很好，逻辑清晰，代码没有bug，当软件体现的算法既优雅又“快速”(理论上或实际问题上的实践，或理想情况下两者兼而有之)，那么计算机科学家会说它真的很漂亮。
这是漂亮代码的一个好的工作定义吗?这是一个悬而未决的问题;我可能错过了一些重要的东西。
数学是美丽的，如果它优雅而富有表现力(比如在一个证明中)。如果一个猜想a的证明需要一个强大的定理B，这个定理B有一个冗长而难以阅读的证明，这并不重要。事实上，这可以使A的证明在它的简单性中更加美丽。
但这对代码不起作用。x=inv(A)*b调用强大的sledgehammer inv(…)，当A是稀疏的时候，这真的很可怕。
当代码不仅看起来漂亮(易于编写、阅读和像乐高玩具一样玩)，而且行为漂亮时，它是漂亮的吗?
贡纳狼
这是我经常在课堂上和我的学生讨论的一个话题，我们所追求的“美”的数量决定了我们学习计算的哪个分支。我在墨西哥最大的大学UNAM工程学院教授操作系统(本科)，在介绍了死锁预防、逃避和检测/恢复的策略后，我提出了这一点:
如果我作为一个数学家，一个强硬的计算机科学家来看待这个话题，死锁的存在本身就是一个丑陋的错误，所以我必须解决它!如果有已知的解决方案(并且有改进的地方)，那么我的职业职责就是去研究它们。
但工程学是理想科学与现实世界相遇的地方。理想的科学自然是美丽的。工程是混乱和油腻的。我们必须平衡解决方案的可行性与现实成本，权衡错误的可能性，根据*大多数*计算机(不是每个人都会设计需要遵循硬实时保证或类似内容的系统)工作的现实调整我们的观察。
有几个讨论点，我们可以为理想而争论，为美丽而争论，或者我们可以让我们的手沾满油污，处理现实世界。这塑造了我们对世界的看法和执行。是的，我们都知道最流行的解决僵局的方法(通常被称为“鸵鸟算法”)清楚地表明，在我们的领域，美貌并不总是赢家。
显示所有2评论