理论计算机科学中最令人困惑的谜题之一被解开

来源：原理

“自敏感度猜想提出以来，它便是所有组合学和理论计算机科学中最令人沮丧和尴尬的开放性问题之一。”德克萨斯大学奥斯汀分校的理论计算机学家Scott Aaronson在一篇博客中写道。

Aaronson提到的猜想是一个与计算机电路的基本构件结构有关的猜想，近30年以来，许多人都试图攻克这一难题，写出了一篇又一篇长而复杂的论文，但结果都以失败告终。然而，在一篇于本月初发表在arXiv上的论文中，年轻的数学家黄皓以令人惊叹的简洁方法解决了这一猜想。

1.

这个猜想与布尔函数有关，布尔函数是一系列将一串输入位（0和1）转换成一个独个的输出位的规则。比如它的规则可以是，当输入字符串中的比特位全部为1时，那么输出为1，其他情况则输出为0；又比如它可以是，当输入字符串中含有1的个数为偶数时，那么输出为0，否则输出为1。

试想你正在填写一份银行贷款的申请表，你需要填写一系列“是/否”问题，银行会根据你填写的答案进行评判，然后决定你是否有资格申请贷款。这个过程就是一个布尔函数，你的每一道“是/否”问题的答案都是一个输入位，银行的最终决定是输出位。

为了度量布尔函数的复杂性，计算机科学家已发展出许多不同的度量方法，每一种都针对的是“输入字符串中的信息会如何决定输出位”这一问题的不同方面。例如布尔函数的“敏感度”所描述的就是当一个单个的输入位被改变时，输出位因此而改变的可能性。

我们可以用上面的银行贷款例子来作进一步解释。假如你的申请没有通过，于是你想，要是你修改某个问题的答案，是否就可以改变结果？比如在关于收入的问题上，你谎称自己年薪百万，而实际上却并没有，会不会就可以通过贷款申请？如果修改这个问题的答案真的能反转结果，那么计算机科学家会说，布尔函数对这个特定位的值是“敏感的”。

再比如说在这张长长的申请表中有7个关键的问题，如果你对这7个问题的任何一个撒谎都能反转结果，那么对于你的贷款概况而言，布尔函数的敏感度为7。

敏感度只是测量布尔函数的复杂性的其中一个度量，每种度量都为审视布尔函数的结构提供了一个独特的视角。然而计算机科学家发现，几乎所有这些度量都符合一个统一的框架，也就是说其中的任何一个度量的值都可被用来大致衡量其他度量的值，而敏感度似乎是唯一的例外。

1992年，希伯来大学的Noam Nisan和罗格斯大学的Mario Szegedy推测，敏感度也是符合这一框架的。但这么多年来，一直没有人能证明这一点，这个猜想成为了布尔函数研究中最突出的待解问题。

现在，埃默里大学的数学家黄皓利用立方体上的点的组合学，用仅仅两页纸的篇幅，巧妙地完成了论证。他证明了敏感度猜想！

2.

1992年，Craig Gotsman和Nati Linial就发现，可以将敏感度猜想的证明归结为解答关于不同维度下的立方体的简单问题。有一种方法能将含有n个0和1的字符串转换到n维立方体上的点上，那就是直接用n个字符位作为点的坐标。

例如你有4个2位的字符串——00、01、10和11，就可以分别对应于二维平面上的一个正方形的四个角——(0,0)、(0,1)、(1,0)和(1,1)；再比如你有8个3位的字符串，就可以对应于一个三维立方体的8个角，更高维度也可依次类推。

○ 举例说明如何将n个输入位表示成一个n维立方体的坐标，如果电路输出为1，则灯泡亮蓝光；如果电路输出为0，则灯泡亮红光。

而布尔函数可以被视作为用两种不同颜色（例如红色表示0，蓝色表示1）来对这些角进行着色的规则。如果将一个立方体超过一半的的角着上红色，那么是否总有一些红点会与许多其他的红点相连？

如果这个集合中所包含的角的个数恰好是那个立方体的一半，那么就可能没有一个角是相连的。就比如在三维立方体的8个角中，(0,0,0)、(1,1,0)、(1,0,1)和(0,1,1)这四个点都位于对角线上。但是，只要立方体中超过一半的点被着上了红色，那么这些红点之间就必然有一些是相连的。问题是：这些连接是如何分布的？至少会有一个是高度相连的点吗？

○ 立方体中有一半以上的点被着上了红色。

黄皓决定用矩阵来追踪哪些点是相连的，他想到了用一种已有200年历史的数学方法——柯西交错定理（Cauchy interlace theorem），这种方法能将矩阵的特征值与子矩阵的特征值联系起来。上个月他突然意识到，他只要改变矩阵中的一些数字的符号，就可以完整地将这种方法一直推演到最终结果。通过这种方法，他成功地证明了在一个n维立方体中，任何超过一半的点的集合，都会有某个点至少与其他√n个点相连接——从这个结果可以立即得出敏感度猜想。

3.

人们或许会以为，证明这样一个已经存在了30年难题，它的论证过程一定非常冗长，而且肯定极度晦涩难懂。有的同行甚至在读之前就做好了读完之后发现自己什么都没看懂的准备。

然而，黄皓的证明却异常简明，许多研究人员一看就全明白了。可以说，这一结果用来证明敏感度猜想绰绰有余，它所蕴含的能力或许能让我们对复杂性度量产生新的见解，是我们在未来解答布尔函数分析中的其他问题的一个强有力工具。

而且最重要的是，黄皓的研究结果消除了人们一直以来的一个担忧，那就是在复杂性度量的世界中，敏感度是否是某种奇怪的异常值。想必有了这个结果后，许多计算机科学家都能睡得更安稳了。

参考链接：

https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/

https://www.scottaaronson.com/blog/?p=4229

https://arxiv.org/abs/1907.00847

张亚勤、刘慈欣、周鸿祎、王飞跃、约翰.翰兹联合推荐

这是一部力图破解21世纪前沿科技大爆发背后的规律与秘密，深度解读数十亿群体智能与数百亿机器智能如何经过50年形成互联网大脑模型，详细阐述互联网大脑为代表的超级智能如何深刻影响人类社会、产业与科技未来的最新著作。

《崛起的超级智能;互联网大脑如何影响科技未来》2019年7月中信出版社出版。刘锋著。了解详情请点击：【新书】崛起的超级智能：互联网大脑如何影响科技未来

未来智能实验室是人工智能学家与科学院相关机构联合成立的人工智能，互联网和脑科学交叉研究机构。

未来智能实验室的主要工作包括：建立AI智能系统智商评测体系，开展世界人工智能智商评测；开展互联网（城市）云脑研究计划，构建互联网（城市）云脑技术和企业图谱，为提升企业，行业与城市的智能水平服务。

  如果您对实验室的研究感兴趣，欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/