七年思考，两页证明，华人学者解开计算机领域30年难题：布尔函数敏感度猜想

机器之心报道

参与：李泽南、路

近日，美国艾默里大学计算机与数学科学系教授黄皓（Hao Huang）用一篇短短 6 页的论文「轻松」证明了困扰理论计算机领域数十年的布尔函数敏感度猜想，引发了计算机和数学领域社区的广泛关注。布尔函数敏感度猜想是理论计算机科学中近三十年来最重要，最令人困惑的开放性问题之一。

论文长度仅有 6 页，其核心证明内容只有两页，不过黄皓为了解决这个问题花费了 7 年时间的思考。

本月初，一篇仅有 6 页的论文悄悄登上了 arXiv，随之而来的是学界的轰动。这篇由华人学者黄皓所著的研究解决了困扰计算机科学领域的难题：布尔函数的敏感度猜想（sensitivity conjecture），而这篇论文中实际的证明部分只有两页纸。

完成这一壮举的数学家黄皓来自广东汕头，他 2007 年本科毕业于北京大学，博士就读于加州大学洛杉矶分校（UCLA），师从著名数学家 Benny Sudakov 教授。黄皓于 2012 年获得博士学位，2012-2014 年受邀访问普林斯顿高等研究院，现担任美国艾默里大学数学系助理教授。其主要研究领域包括极值组合、图论及理论计算机。已经在 JCTB、JCTA、Combinatorica、SIAM J. Discrete Math 等国际著名期刊上发表及接受发表论文 20 余篇。

布尔函数的敏感度猜想主要涉及计算机电路的基础构造块结构，迄今已快 30 年。在这二十余年中，该猜想难倒了许多优秀的计算机科学家，而黄皓提出的证明方法简单到可以用一篇推文总结：

CMU 计算机科学系教授 Ryan O'Donnell 发推概括了这篇证明。（图源：https://twitter.com/BooleanAnalysis/status/1145837576487612416）

使用有 200 年历史的方法解决了 30 年历史的重量级猜想，有关布尔函数敏感度的证明让我们感受到了数学之美。人们对于黄皓的论证纷纷表示感叹：「这是我们看到过最美丽的两页证明。」

敏感度猜想涉及布尔函数，布尔函数描述如何基于对布尔输入的某种逻辑计算确定布尔值输出，在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。

图源：http://jandan.net/2019/07/13/sensitivity-conjecture.html

这一猜想可以简单表述为：存在一个多项式 P，对所有的布尔函数 f，都成立 bs(f)≤P[s(f)]！

敏感度猜想

法国国家科学研究中心 Claire Mathieu 用生动的例子介绍了布尔函数及其敏感度。

当你在银行贷款申请书上填写一系列 yes/no 问题的时候，填写完之后，银行工作人员将对你的填写结果进行评分，然后告知你是否符合贷款条件。这一过程就是一个布尔函数：你的答案是输入 bit，银行工作人员的决策是输出 bit。

如果你的申请被拒，你可能会觉得如果在回答某一个问题时撒谎是否就可以改变最后的结果，比如在你实际上挣钱数量不超过 5 万美元时却表示超过这一数目。如果该谎言能够改变最终决策结果，那么这一布尔函数就对特定 bit 的值「敏感」。假如有七个不同的谎言每一个都可以导致最终决策结果反转，那么这一布尔函数的敏感度就为 7。

计算机科学家将该布尔函数的敏感度定义为：当查看所有不同贷款资料时所得到的最大敏感度值。某种程度上，它可以计算在模棱两可的情况下多少问题是真正重要的，这些情况包括只要稍微改变即可情况反转的申请。

敏感度通常是最容易计算的复杂度度量指标，但是它并非唯一富有启发性的指标。例如，银行工作人员不让你填写纸质申请，而是进行面谈，先问简单的问题，再根据你的回答进行后续的提问。这时候银行职员在进行决策前需要提问的最大问题数量就是布尔函数的查询复杂度（query complexity）。

这一度量指标在很多场景下都会出现，例如医生在得出诊断结果之前想让病人尽可能少地进行检查，或者机器学习专家想让算法在进行物体分类之前尽可能少地查看物体的特征。「在大量场景中，如诊断场景或学习场景，底层规则的 query 复杂度低是非常值得庆幸的。」O'Donnell 表示。

其他度量包括寻找将布尔函数写为数学表达式的最简单方法，或者说计算银行职员应向上司展示多少个答案，才能证明他们做了正确的贷款决定。这里甚至还有量子物理版本的查询复杂度，即银行职员可以在同一时间询问多个问题的「叠加」。找到这种度量与其他复杂度的关系，可以帮助研究人员了解量子算法的局限性。

除了敏感度之外，计算机科学家已经证明了所有这些度量都是紧密关联的。具体而言，它们之间存在多项式关系——例如一个度量可能大致是另一个度量的平方或立方或平方根。

只有敏感度固执地拒绝适应这种简洁的表示。很多研究人员怀疑敏感度与其他度量之间也存在多项式关系，但人们一直无法证明确实不存在奇特的布尔函数，其敏感度与其他度量具有指数而非多项式关系。这意味着敏感度度量远小于其他度量。

「这一问题已经困扰了人们三十年。」德克萨斯大学奥斯汀分校计算机科学教授 Scott Aaronson 说道。

寻找解法

黄皓在 2012 年末与普林斯顿高等研究院数学家 Michael Saks 共进午餐的时候听闻了敏感度猜想，彼时前者还是一名博士后。他立即被这一猜想的简洁和优雅所吸引了。「从那一刻起，我就开始沉迷于思考这个问题了。」黄皓说道。

黄皓将敏感度猜想加入了他感兴趣问题的「秘密清单」中，每当他学习新的数学工具时，他都会思考这些方法是否会对解决敏感度猜想有所帮助。「每次我发表新的论文之后，我总会回过头来看看这个问题，」黄皓表示。「当然，我也经常在研究一番之后选择放弃，然后回到更为现实的问题上来。」

数学家黄皓在里斯本。

黄皓明白，正如研究社区普遍认为的一样，如果数学家可以证明一个有关不同维度立方体上点集合的猜想，那么敏感度猜想就可以得到解决。从一个 n 个 0 和 1 组成的序列到 n 维立方体上的点有一种自然的方法：只需使用 n 个 bit 作为点的坐标。

例如，有四个两位字符串 00、01、10 和 11，分别对应二维平面中正方形的四个角：(0,0)、(0,1)、(1,0) 和 (1,1)。同样，八个三位字符串分别对应三维立方体的八个角……以此类推。布尔函数可以被认为，用两种不同颜色为这些角进行着色的规则（比如为 0 涂红色，1 涂上蓝色）。

1992 年，现任新泽西理工计算机学院院长 Craig Gotsman 和希伯来大学计算机科学教授 Nati Linial 找出了证明敏感度猜想的思路：通过回答一个有关不同维度立方体的问题将敏感度猜想大大简化，如果你选择将超过一半的立方体尖角同时涂为红色，是否总是有一些红色点是与其他红色点相连接？（在这里，「连接」表示通过立方体的边相连，而不是通过任何对角线。）

如果你选择刚好一半的立方体尖角，则很可能红色点并不会相连接。例如，在三维立方体的八个角中，(0,0,0), (1,1,0), (1,0,1) 和 (0,1,1) 这四个点只是通过对角线相连。但是只要立方体中超过一半的点被涂成红色，那么肯定会出现相连接的红色点。问题在于：这些连接是如何分布的？是否存在一个高度连接的点？

2013 年，黄皓认为理解这一问题的最佳路径是，使用矩阵表示网络（矩阵可以追踪相连的点），并检测矩阵特征值。之后五年，他一直试验这个思路，但都没有成功。

2018 年，黄皓决定使用柯西交错定理（Cauchy interlace theorem），该定理将矩阵特征值和子矩阵特征值关联起来，因此成为研究立方体及其尖角子集的完美工具。黄皓决定向美国国家科学基金会提交申请，以进一步探索这一思路。

随后在上个月，当他坐在马德里的一家旅馆中撰写申请报告时，他突然意识到自己可以通过简单地改变矩阵中一些数字的符号来直接解决问题。通过这种方式，他可以证明在 n 维立方体中超过一半点的任何集合中，会有一些点和其他点有至少√n 个连接，敏感度猜想问题的证明就从这里开始。

当黄皓的论文进入 Claire Mathieu 的收件箱时，她的第一反应是「哦——哇」，她说道：「当一个问题已经存在了 30 年，而每个人都已经听闻过的时候，我们自然认为证明它的方法会看起来冗长而复杂，或者非常高深。」她打开论文并期待看到无法理解的内容。

但是，对于 Mathieu 和其他很多研究者来说，这一证明非常简单，可以一次消化。「我希望在今年的秋天在每个硕士级别的组合数学课程中讲授这一内容——一堂课就够了。」Mathieu 表示。

黄皓的研究结果甚至超过了证明敏感度猜想所需的必要程度，其推理应该可以形成有关复杂度度量的新见解。「它充实了我们的工具库，让我们可以试图回答布尔函数分析中的其他问题。」哥伦比亚大学计算机科学教授 Rocco Servedio 说道。

当然，更重要的是黄皓的结果让那些担忧敏感度可能是复杂度度量世界中的异类的人放心了，Servedio 表示。「我认为在这一证明推出以后，很多人终于能睡得着觉了。」

最后，这里是黄皓对布尔函数敏感度猜想的两页纸证明：

更多详情参见论文《Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture》（https://arxiv.org/pdf/1907.00847.pdf）。