原文：https://cacm.acm.org/opinion/what-is-theoretical-computer-science/
作者：Moshe Y. Vardi
译者：Kurt Pan
将理论计算机科学视为数学的一个分支对这门学科是有害的。
我认为自己是一名理论计算机科学家，但维基百科将我描述为“数学家和计算机科学家”。那么我到底是什么？为了回答这个问题，我们必须重新去考量 理论计算机科学（TCS） 的定义，其维基百科将其定义为“计算机科学和数学的一个子领域，专注于计算的抽象数学基础”。我想对这个定义提出质疑。
2023年ACM A.M. 图灵奖得主 Avi Wigderson 在他 2019 年出版的优美著作《数学与计算》中将计算理论定义为“对计算机科学和技术的形式化基础的研究”。这是一个非常宽泛的定义，但那本书的范围其实与该定义并不相符。它提供了一种非常美国中心的 TCS 观点。正如我在其他地方所写的，美国TCS 的范围要比欧洲 TCS 的范围更窄，我觉得这很不幸。
我相信 Avi 对理论计算机科学有着正确且宽泛的定义；它是“对计算机科学和技术的形式化基础的研究”。事实上，如果你浏览 1970 年代 ACM 计算理论研讨会 (STOC) 和 IEEE 计算机科学基础研讨会 (FOCS) 的会议记录，你会发现 TCS 确实是一个非常宽泛的概念。直到 20 世纪 80 年代，随着专门讨论数据库、程序验证等主题的所谓“卫星会议”的激增，STOC 和 FOCS 的范围才缩小，从而导致更狭窄的美式TCS 视角 。
不管 TCS 的广度如何，它是否是数学的一个子领域的问题依然存在。毫无疑问，TCS是抽象的、数学的，但它是数学吗？就此而言，到底数学是什么？众所周知，数学很难定义，所以我更喜欢社会学的定义：数学是数学家所做的事情。 1993 年，作为一名年轻的理论计算机科学家，我获得了Rice大学计算机系的教职。我怀疑我是否会收到Rice大学数学系的这样一份录取。Avi是全球少数在数学系担任主要职位的理论计算机科学家之一。我必须得出结论，TCS 不是数学的一个分支，至少在社会学意义上是这样的。
但我对“TCS 是数学的一个分支”的反对比上述社会学的论证更为深刻。我认为将 TCS 视为数学的一个分支对这门学科是有害的。计算的中心地位源于这样一个事实：自从英国在二战中利用早期计算改变战争潮流以来，计算就是一项在过去 80 年里一直在改变世界的技术。作为计算机科学家，我们应该从物理学而不是数学中寻找灵感。理论物理学是高度数学化的，但它的目的是解释和预测现实世界。未能完成这种“解释/预测”任务的理论最终将被丢弃。类似地，我认为 TCS 的作用应该是去解释/预测现实生活中的计算。我并不是说每一篇 TCS 论文都应该遵守这个标准，但这个标准应该适用于 TCS 的各个分支。我们应该记住20世纪最伟大的数学家和计算机科学家之一约翰·冯·诺伊曼 (John von Neuman) 关于数学完全由内部美学驱动的危险的警告：“这门学科很可能会沿着最小阻力的路线发展，这是一个严重的危险。”
例如，考虑一下计算复杂性理论——Avi 书的主要焦点所在——我认为是计算机科学中最优雅的理论。这个理论侧重于根据资源使用（通常是时间和空间）对计算问题进行分类。其皇冠上的明珠之一是 NP 完全性的概念，其具体化了检验解和寻找解之间的差异。典型的 NP 完全问题是布尔可满足性问题 (SAT)，判定给定的布尔公式（具有 AND 和 NOT 等布尔门）是否有其输入变量的 0 、 1赋值，使得该公式输出值1。 库克在 1971 年证明了 SAT 是 NP 完全的，这个问题被认为是计算困难的。
然而在过去的 30 年里，我们在 SAT 求解方面取得了巨大的进步，这已成为当今的工业现实。然而，NP 完全性理论并不能解释或预测 SAT 求解器不合理的有效性。尽管最近有一些超越最坏情况复杂性的努力，但这种方法仍然是计算复杂性分析的流行方法，但它对揭示“真实复杂性”的作用其实很少。
所以，我不认为自己是一个数学家。我完全属于计算机科学阵营。
