两页纸就解开了一个数十年之久的计算机科学难题

本月发布在网上的一篇论文解决了近30年来关于计算机电路基本构件结构的猜测。多年来，这一“敏感性”猜想难倒了许多最杰出的计算机科学家，然而新的证据如此简单，以至于一位研究人员在一条推文中总结了这一猜想。

德克萨斯大学奥斯汀分校(University of Texas，Austin)的斯科特·亚伦森(Scott Aaronson)在一篇博客文章中写道：“这个猜想一直是组合学和理论计算机科学中最令人沮丧和尴尬的公开问题之一。”他在一封电子邮件中补充说：“试图解决这个问题但失败的人的名单就像是离散数学和理论计算机科学的名人录。”

猜想涉及布尔函数，即将一串输入位(0和1)转换为单个输出位的规则。一条这样的规则是在任何输入位为1的情况下输出1，否则输出0；另一条规则是如果字符串具有偶数个1，则输出0，否则输出1。哥伦比亚大学的Rocco Servedio说，每一个计算机电路都是布尔函数的某种组合，使它们成为“你在计算机科学中所做的任何事情的砖块和砂浆”。

多年来，计算机科学家已经开发出许多方法来测量给定布尔函数的复杂性。每个度量捕获输入字符串中的信息如何确定输出位的不同方面。例如，粗略地说，布尔函数的“灵敏度”跟踪翻转单个输入位将改变输出位的可能性。“查询复杂度”计算您必须询问多少个输入位才能确定输出。

每个度量都为布尔函数的结构提供了唯一的窗口。然而，计算机科学家发现，几乎所有这些衡量标准都符合一个统一的框架，因此它们中任何一个的价值都是对其他标准价值的粗略衡量。只有一项复杂性指标似乎不符合：敏感度。

1992年，耶路撒冷希伯来大学的诺姆·尼桑(Noam Nisan)和现任罗格斯大学(Rutgers University)的马里奥·塞格迪(Mario Szegedy)推测，敏感性确实符合这个框架。但没人能证明这一点。Servedio说：“我想说，这可能是布尔函数研究中悬而未决的问题。”

卡内基梅隆大学(Carnegie Mellon University)的瑞安·奥唐奈(Ryan O‘Donnell)说：“人们写了冗长而复杂的论文，试图取得最微小的进展。”

现在，埃默里大学(Emory University)数学家黄浩(音译)用一篇关于立方体上点的组合学的巧妙而初级的两页论证证明了这一敏感性猜想。法国国家科学研究中心的克莱尔·马蒂厄(Claire Mathieu)在接受Skype采访时写道：“它太美了，就像一颗珍贵的珍珠。”

Aaronson和O‘Donnell都称黄的论文是敏感性猜想的“书”证明，指的是Paul Erdő的天书概念，上帝在书中写下了每个定理的完美证明。Aaronson写道：“我发现很难想象，即使是上帝也知道如何用比这更简单的方式来证明敏感性猜想。”

马修说，想象一下，你正在填写一系列关于银行贷款申请的是/否问题。当你完成后，银行家会给你的结果打分，并告诉你是否有资格获得贷款。这个过程是一个布尔函数：您的答案是输入位，银行家的决定是输出位。

如果你的申请被拒绝，你可能会想，你是否可以通过在一个问题上撒谎来改变结果--也许是通过声称你赚了超过5万美元，而你实际上没有。如果这个谎言会颠覆结果，计算机科学家说，布尔函数对这个特定位的值是“敏感的”。比方说，如果你可以说七个不同的谎言，每个谎言都会分别翻转结果，那么对于你的贷款配置文件，布尔函数的敏感度是7。

计算机科学家将布尔函数的总体敏感度定义为在查看所有不同可能的贷款概况时的最大敏感值。在某种意义上，这一衡量标准计算出在最边缘的情况下，有多少问题是真正重要的-。

如果这些应用程序稍有不同，它们很容易就会转向另一个方向。

灵敏度通常是最容易计算的复杂性度量之一，但它远不是唯一具有启发性的度量。例如，银行家本可以面试你，而不是递给你一份纸质申请表，从一个问题开始，然后根据你的答案来决定下一步要问什么问题。银行家在做出决定之前需要问的最多的问题是布尔函数的查询复杂性。

这一措施出现在许多环境中-例如，医生可能希望在得出诊断之前让患者进行尽可能少的测试，或者机器学习专家可能希望算法在对对象进行分类之前检查尽可能少的对象特征。“在很多情况下--诊断情况或学习情况--如果基本规则…。具有较低的查询复杂度。“O‘Donnell说。

其他措施包括寻找最简单的方法将布尔函数写成数学表达式，或者计算银行家必须向老板展示多少答案才能证明他们做出了正确的贷款决定。甚至还有一个量子物理版本的查询复杂性，银行家可以同时提出几个问题的“叠加”。弄清楚这一衡量标准与其他复杂性衡量标准之间的关系，有助于研究人员理解量子算法的局限性。除了敏感度之外，计算机科学家证明了所有这些措施都是紧密相连的。具体地说，它们彼此之间具有多项式关系-例如，一个度量值可能大致是另一个度量值的平方、立方或平方根。只有敏感顽固地拒绝融入这种巧妙的描述。许多研究人员怀疑它确实属于它，但他们不能证明外面没有奇怪的布尔函数，它们的灵敏度与其他度量呈指数关系，而不是多项式关系，在这种情况下，这意味着灵敏度度量比其他度量小得多。

“这个问题30年来一直是人们的眼中钉，”Aaronson说。

黄在2012年底与数学家迈克尔·萨克斯(Michael Saks)在高等研究院(Institute For Advanced Study)共进午餐时听说了敏感性猜测，当时黄是该研究所的博士后研究员。他立刻被这个猜想的简约和优雅迷住了。“从那一刻开始，我开始沉迷于思考这件事，”他说。

黄将敏感性猜想添加到他感兴趣的问题的“秘密清单”中，每当他了解到一个新的数学工具时，他就会考虑它是否会有帮助。“每次我发表一篇新论文后，我总是会回到这个问题上来，”他说。“当然，过了一段时间，我会放弃，去解决一些更现实的问题。”黄知道，就像更广泛的研究界一样，如果数学家能够证明关于不同维度立方体上的点集合的一个容易陈述的猜想，那么敏感性猜想就可以解决。从n个0和1组成的字符串到n维立方体上的一个点有一种自然的方法：只需使用n位作为该点的坐标。

例如，四个两位字符串-00、01、10和11-对应于二维平面中正方形的四个角：(0，0)、(0，1)、(1，0)和(1，1)。同样，8个3位字符串对应于三维立方体的8个角，在更高的维度中依此类推。反过来，布尔函数可以看作是用两种不同的颜色给这些角着色的规则(比如，红色代表0，蓝色代表1)。

1992年，现任新泽西理工学院的克雷格·戈茨曼(Craig Gotsman)和希伯来大学(Hebrew University)的纳蒂·利尼尔(Nati Linial)想出了证明敏感性猜想的方法，可以归结为回答一个关于不同维度的立方体的简单问题：如果你选择任何一个立方体超过一半的角的集合，并将它们涂成红色，是否总有一些红点与许多其他红点相连？(在这里，我们所说的“连接”是指这两个点共享立方体的一条外边，而不是穿过一条对角线。)。

如果您的集合正好包含立方体的一半角，则它们可能都不会连接。例如，在三维立方体的八个角中，四个点(0，0，0)、(1，1，0)、(1，0，1)和(0，1，1)都位于彼此的对角线上。但是，只要任何维度的立方体中超过一半的点被涂成红色，红色点之间的一些连接就会弹出。问题是：这些连接是如何分布的？会不会至少有一个高度连接的点？

2013年，黄开始认为理解这个问题的最佳途径可能是通过标准方法，即用一个追踪哪些点相连的矩阵来表示网络，然后检查一组称为矩阵特征值的数字。五年来，他一直在反复考虑这个想法，但没有成功。他在Aaronson的博客文章中评论道：“但至少想一想，我很快就睡着了很多个晚上。”

然后在2018年，黄想到使用一项有200年历史的数学作品，名为柯西交错定理，它将矩阵的特征值和子矩阵的特征值联系起来，使其有可能成为研究立方体及其角点子集之间关系的完美工具。黄决定向国家科学基金会申请拨款，以进一步探索这一想法。