2021年理论计算机最高荣誉“哥德尔奖”出炉！两位华人学者获奖，AdaBoost算法曾获该奖

作者 | 琰琰、陈大鑫

哥德尔理论计算机科学杰出论文奖由EATCS和ACM SIGACT联合主办。该奖项的设立是为了纪念库尔特·哥德尔（Kurt Gödel）在数理逻辑方面做出的重大贡献，因而以他的名字而命名。哥德尔在约翰·冯·诺依曼去世前给他写了一封信，表达了他对数理逻辑的兴趣以及他的重大发现，这个发现也就是后来著名的“P/NP" 问题。

哥德尔奖获奖论文必须在理论计算机领域具有开创性重大贡献；同时须在获奖前14年内在学术期刊上正式发表。哥德尔奖是理论计算机领域最负盛名的奖项，2003年，Yoav Freund和Robert Schapire曾因提出著名的AdaBoost算法获得了当年的“哥德尔奖”。

评审委员会由6名成员组成，分别由EATCS主席与ACM SIGACT主席提名。评选委员会对被提名者进行严格的评审，并最终确定当年的获奖者。

该奖项每年颁发一次，在自动机、语言和程序设计国际学术讨论会（ICALP）和ACM计算理论年会（STOC）上轮流颁发，今年则是轮到了STOC，另外奖金包括5000美元。

1 2021哥德尔奖

今年一共有下面三篇论文共同获得了哥德尔奖：

其中获奖论文《Complexity of Counting CSP with Complex Weights 》的两位作者均是华人学者。

论文地址：https://dl.acm.org/doi/10.1145/2213977.2214059#pill-authors__contentcon

论文作者：Jin-Yi Cai

Jin-Yi Cai 目前是斯坦福大学计算机科学系教授。在此之前，他在耶鲁大学、普林斯顿大学和纽约州立大学水牛城分校担任教师职位。曾就读于复旦大学、坦普尔大学和康奈尔大学，并于1986年获得博士学位。

他先后获得过总统青年调查员奖、斯隆计算机科学奖学金，古根海姆奖，Morningside Silver 数学奖以及洪堡美国资深科学家研究奖。还被选为ACM和AAAS成员。目前他是《计算机与系统科学杂志》（JCSS）等很多期刊杂志主编，主要从事计算复杂性理论研究，已撰写和发表研究论文100余篇。

个人主页：https://simons.berkeley.edu/people/jin-yi-cai

论文作者：Xi Chen

Xi Chen是哥伦比亚大学计算机科学系副教授。在此之前，他是普林斯顿大学和南加州大学高级研究所的博士后研究员。Xi Chen曾于清华大学获得物理/数学理学学士学位和计算机科学博士学位。他师从张钹院士，是姚期智教授领导的计算机理论研究所的成员之一。

其研究兴趣包括算法博弈论/经济学、复杂性理论。相关研究曾获得过 NSF CAREER奖、斯隆研究奖学金，以及EATCS Presburger奖。

个人主页：

http://www.cs.columbia.edu/~xichen/Homepage/Welcome.html

其他两篇获奖论文：

• The Complexity of the Counting Constraint Satisfaction Problem

作者：Andrei Bulatov，西蒙菲莎大学计算机科学系教授

• An Effective Dichotomy for the Counting Constraint Satisfaction Problem

论文一作：Martin E. Dyer，英国利兹大学教授，曾获得Fulkerson 奖。

论文二作：David Richerby，埃塞克斯大学计算机科学与电气工程系讲师，于2003年获得剑桥大学博士学位。

以上三篇论文均涉及约束满足问题（Constraint Satisfaction Problems，简称CSP)的研究。约束满足是计算机科学中的一个重要课题，布尔可满足性（ Boolean Satisfiability）和图着色（Graph Coloring）等相关的大量问题都可以用它来解决。

获奖介绍中写道，以上三篇论文将计算CSP复杂度分类研究推向了高潮，它们提出了一种可计算CSP类型问题的复杂度二分法定理（Complexity Dichotomy Theorem）。这种二分法定理所涉及的问题类别非常广泛，包括所有的counting CSPs，所有类型的graph homomorphisms以及自旋系统(spin systems,它涉及统计物理中的各种问题）等等。

对于所有这些问题，这个定理给出了一个复杂度二分法分类：各类中的每个问题要么在多项式时间内可解，要么在#P-hard内可解。

2 哥德尔和其不完备性定理

哥德尔是奥地利裔美国人，被誉为是20世纪最伟大的数学家和逻辑学家之一。在逻辑学中的地位，一般都将他与亚里士多德相比；在数学中的地位，爱因斯坦把哥德尔的贡献与他本人对物理学的贡献相提并论。

哥德尔本人最杰出的贡献莫过于他在1931年提出来的哥德尔不完备性定理，该定理一共包含两条。

第一定理：任意一个包含一阶谓词逻辑与初等数论（皮亚诺算术公理）的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。

第二定理：任何逻辑自洽的形式系统，只要蕴涵皮亚诺算术公理，它就不能用于证明其本身的自洽性（无矛盾性）。

这一理论使数学基础研究发生了划时代的变化，更是现代逻辑史上很重要的一座里程碑。该定理与塔尔斯基的形式语言的真理论，图灵机和判定问题，被赞誉为现代逻辑科学在哲学方面的三大成果。 哥德尔本人只证明了以上定理的一个较弱版本。

（注：该定理并不意味着任何有意义的公理系统都是不完备的。该定理需假设公理系统可以“定义”自然数。不过并非所有系统都能定义自然数，就算这些系统拥有包括自然数作为子集的模型。）

另外值得一提的是，20世纪20年代，在集合论不断发展的基础上，大数学家希尔伯特向全世界的数学家抛出了个宏伟计划，其大意是建立一组公理体系，使一切数学命题原则上都可由此经有限步推定真伪，这叫做公理体系的“完备性”；希尔伯特还要求公理体系保持“独立性”（即所有公理都是互相独立的，使公理系统尽可能的简洁）和“无矛盾性”（即相容性，不能从公理系统导出矛盾）。

1931年，在希尔伯特提出计划不到3年，年轻的哥德尔就使希尔伯特的梦想变成了令人沮丧的噩梦。因为哥德尔带着他的不完全性定理来了：任何无矛盾的公理体系，只要包含初等算术的陈述，则必定存在一个不可判定命题，用这组公理不能判定其真假。也就是说，“无矛盾”和“完备”是不能同时满足的！

可以说哥德尔不完全性定理一举粉碎了数学家两千年来的信念。他告诉我们，真与可证是两个概念。可证的一定是真的，但真的不一定可证。某种意义上，不完全性的阴影将永远伴随着我们。

但是哥德尔不完全性定理的影响远远超出了数学的范围。它不仅使数学、逻辑学发生革命性的变化，引发了许多富有挑战性的问题，而且还涉及哲学、语言学和计算机科学，甚至宇宙学。2002年8月，霍金在北京举行的国际弦理论会议上发表了题为《哥德尔与M理论》的报告，认为建立一个单一的描述宇宙的大统一理论是不太可能的，这一推测也正是基于哥德尔不完全性定理。

有意思的是，在人工智能领域，哥德尔不完全性定理是否适用也成为了人们议论的焦点。1961年，牛津大学的哲学家卢卡斯提出，根据哥德尔不完全性定理，机器不可能具有人的心智。他的观点激起了很多人反对。他们认为，哥德尔不完全性定理与机器有无心智其实没有关系，但哥德尔不完全性定理对人的限制，同样也适用于机器倒是事实。

关于哥德尔本人最常被外人津津乐道的一件事就是在普林斯顿等研究院时，哥德尔和爱因斯坦成为了经常一块儿散步的一对忘年交。那是在爱因斯坦去世前的十几年，从1940年，哥德尔正式受聘到普林斯顿高研院开始，一直到爱因斯坦去世。爱因斯坦晚年时有一段话，可看出他对哥德尔的欣赏程度：

我自己的研究已经没有太大进展，我之所以每天还到高等研究院来，只是为了与哥德尔一起散步回家。

在国内，关于哥德尔最为大家熟知的书籍大概就是：《哥德尔艾舍尔巴赫:集异璧之大成》一书，想必大家都畅读过。

1951年在授予哥德尔爱因斯坦勋章时，冯·诺依曼评价说道：“哥德尔在现代逻辑中的成就是非凡的、不朽的——他的不朽甚至超过了纪念碑，他是一个里程碑，是永存的纪念碑。”

参考链接：

https://twitter.com/eatcs_secretary/status/1391733228143251459