分两页解决数十年的旧计算机科学猜想

本月在线发表的一篇论文解决了关于计算机电路基本构建模块的结构已有近30年的推测。多年来，这种“敏感性”猜想困扰了许多最杰出的计算机科学家，但是新证据是如此简单，以至于一位研究人员在一条推文中对其进行了总结。

“这个猜想一直是所有组合学和理论计算机科学中最令人沮丧和尴尬的公开问题之一，”德克萨斯大学奥斯汀分校的斯科特·亚伦森在博客中写道。他在一封电子邮件中补充说：“尝试解决该问题并失败的人的名单就像离散数学和理论计算机科学的人一样。”

该猜想涉及布尔函数，即用于将一串输入位（0和1）转换为单个输出位的规则。一个这样的规则是，如果任何输入位为1，则输出1；否则，输出0。另一个规则是，如果字符串的偶数为1，则输出0，否则为1。哥伦比亚大学的Rocco Servedio说，每个计算机电路都是布尔函数的某种组合，使它们成为“计算机科学领域的基础”。

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

每个度量为布尔函数的结构提供了一个唯一的窗口。然而，计算机科学家发现，几乎所有这些措施都适用于一个统一的框架，因此，其中任何一项的价值都可以粗略衡量其他各项的价值。似乎只有一种复杂性度量不适合：敏感性。

1992年，耶路撒冷希伯来大学的Noam Nisan和现为罗格斯大学的Mario Szegedy猜想，敏感性确实符合该框架。但是没有人能证明这一点。 Servedio说：“这可能是布尔函数研究中的一个悬而未决的开放性问题。”

卡内基梅隆大学的赖安·奥唐奈尔说：“人们写了冗长而复杂的论文，试图取得最小的进步。”

现在，埃默里大学的数学家黄浩用一个巧妙但基本的两页论证（关于立方点上的组合）证明了敏感性猜想。法国国家科学研究中心的克莱尔·马修（Claire Mathieu）在接受Skype采访时写道：“它就像美丽的珍珠一样美丽，”。

Aaronson和O'Donnell都把Huang的论文称为敏感性猜想的“书”证明，是指PaulErdős关于天书的概念，其中上帝为每个定理写了完美的证明。 “我很难想象甚至上帝也知道如何以比这更简单的方式证明敏感性猜想，”亚伦森写道。

猜想，Mathieu说，您正在填写一系列关于银行贷款申请的是/否问题。完成后，银行家将对您的结果进行评分，并告诉您您是否有资格获得贷款。此过程是布尔函数：您的答案是输入位，而银行家的决定是输出位。

如果您的申请被拒绝，您可能会想知道是否可以通过一个问题来改变结果-也许是声称自己确实没有赚到超过50,000美元。计算机科学家说，如果那个谎言会推翻结果，则布尔函数对特定位的值“敏感”。例如，如果您可以告诉我们有七个不同的谎言，每个谎言将分别翻转结果，那么对于您的贷款配置文件，布尔函数的敏感度为七个。

计算机科学家将布尔函数的整体灵敏度定义为在查看所有不同的可能贷款配置文件时的最大灵敏度值。从某种意义上说，这种衡量方法可以计算出在最极端的情况下真正重要的问题有多少个，如果应用之间的差异稍有不同，则这些应用很容易以相反的方式摆弄。

灵敏度通常是最简单的计算复杂度的方法之一，但远非唯一的启发性方法。例如，银行家可能没有面试您的书面申请，而是采访了您，从一个问题开始，然后使用您的答案来确定接下来要问的问题。银行家做出决定前需要提出的最多问题是布尔函数的查询复杂度。

这种措施产生于许多设置中，例如，医生可能希望在诊断之前将患者送去进行尽可能少的测试，或者机器学习专家可能希望算法来检查尽可能少的对象特征在分类之前。 O’Donnell说：“在很多情况下-诊断情况或学习情况-如果基本规则...查询复杂度低，您将感到非常高兴。”

其他措施包括寻找最简单的方法来将布尔函数编写为数学表达式，或者计算银行家必须向老板证明要做出正确贷款决定的答案。甚至还有查询复杂度的量子物理学版本，其中银行家可以同时提出几个问题的“叠加”。弄清楚该度量与其他复杂性度量之间的关系，已帮助研究人员了解了量子算法的局限性。

除了敏感性以外，计算机科学家证明了所有这些措施都是紧密相连的。具体来说，它们彼此之间具有多项式关系-例如，一个量度可能大致是另一个量度的平方或立方或平方根。只有敏感性顽固地拒绝适合这种简洁的特征。许多研究人员怀疑它确实存在，但是他们无法证明那里没有奇怪的布尔函数，其敏感性与其他度量具有指数关系而不是多项式关系，在这种情况下，这意味着敏感性度量在很大程度上比其他措施小。

亚伦森说：“这个问题困扰着人们三十多年。”

Huang于2012年底在高级研究所与数学家Michael Saks共进午餐时听说了关于灵敏度的猜想。他立即被猜想的简单和优雅所吸引。他说：“从那一刻起，我就变得非常着迷于此。”

Huang将敏感性猜想添加到了他感兴趣的问题的“秘密列表”中，每当他了解一种新的数学工具时，他就会考虑是否有帮助。他说：“每次发表新论文后，我总是会回到这个问题上来。” “当然，我会在经过一段时间后放弃工作，着手解决一些更现实的问题。”

就像更广泛的研究界一样，黄仁勋知道，如果数学家可以证明关于不同维度的多维数据集上的点的集合很容易陈述，那么敏感性猜想就可以解决。从n个0和1的字符串到n维多维数据集上的一个点，有一种自然的方法：只需将n位用作该点的坐标即可。

例如，四个两位字符串（00、01、10和11）对应于二维平面中正方形的四个角：（0,0），（0,1），（1,0）和（1,1）。同样，八个三位字符串对应于三维多维数据集的八个角，依此类推在更高维度中。反过来，可以考虑使用布尔函数作为对这些角使用两种不同颜色（例如，红色表示0，蓝色表示1）着色的规则。

1992年，现为新泽西理工学院的克雷格·哥茨曼和希伯来大学的纳蒂·里纳利指出，证明敏感性猜想可以简化为回答一个关于不同维度的多维数据集的简单问题：如果选择大于将立方体的一半角都涂成红色，是否总是有一些红点与许多其他红点相连？ （在这里，“连接”是指两个点共享立方体的外边缘之一，而不是跨越对角线。）

如果您的收藏集恰好包含立方体角的一半，则可能没有一个被连接。例如，在三维立方体的八个角中，四个点（0,0,0），（1,1,0），（1,0,1）和（0,1,1）都位于跨越彼此的对角线。但是，只要任何尺寸的立方体中超过一半的点变成红色，就必须弹出红色点之间的某些连接。问题是：这些连接如何分布？至少会有一个高度连接的点吗？

Huang于2013年开始思考，理解此问题的最佳途径可能是通过一种标准方法，即用矩阵表示网络，该矩阵跟踪连接的点，然后检查一组称为矩阵的特征值的数字。五年来，他一直在重新审视这个想法，但没有成功。他在亚伦森（Aaronson）的博客文章中评论说：“但是至少考虑一下可以帮助我在许多晚上迅速入睡。”

然后在2018年，Huang想到了使用200年历史的名为Cauchy隔行定理的数学模型，该模型将矩阵的特征值与子矩阵的特征值相关联，使其成为研究多维数据集与立方体之间关系的理想工具。角落的一个子集。 Huang决定要求国家科学基金会拨款，以进一步探索这一想法。

上个月，当他坐在马德里的一家旅馆里编写资助计划时，他突然意识到，只要切换矩阵中一些数字的符号，他就可以将这种方法完全实现。这样，他就能证明在n维立方体中超过一半点的任何集合中，都会有一些点至少与其他点的$ latex \ sqrt {n} $相关联-从这个结果可以立即得出灵敏度推测。

她说，当黄的纸放到Mathieu的收件箱中时，她的第一个反应是“呃-哦”​​。 “当一个问题已经存在了30年左右，并且每个人都听说过时，证明可能是漫长而乏味且复杂的，或者是非常深刻的。”她打开纸，希望什么都不懂。

但是证明很简单，Mathieu和许多其他研究人员可以一口气消化一下。她在Skype上说：“我希望今年秋天将在每门硕士水平的组合学课程中通过一次讲座进行教授。”

Huang的结果甚至比证明敏感性猜想所需的结果还要强大，并且这种能力应该会带来有关复杂性度量的新见解。 Servedio说：“它增加了我们的工具包，可能试图回答布尔函数分析中的其他问题。” Servedio说，最重要的是，Huang的结果使人们不再担心在复杂性度量世界中敏感性是否可能是一个奇怪的异常值。 “我听说那天晚上，很多人都睡得更香。”