只用2页纸，北大校友攻破计算机30年难题！看懂仅需线性...

只用2页纸，北大校友攻破计算机30年难题！看懂仅需线性代数基础 原创 量子位 2019-07-28 12:30:41

边策 发自 凹非寺
量子位 报道 | 公众号 QbitAI

数学世界中有很多猜想，比如哥德巴赫猜想、黎曼猜想，有些问题已经困扰了全人类几百年。
如果某一天，某个人突然跳出来说：“我只用几页纸，就证明了XX猜想。”大家一定会觉得这人是个“民科”。
最近，有位华人数学家黄皓宣布，他证明了一个困扰计算机理论界30年的猜想，而且只用了两页纸。乍一看到这则消息，可能很多人的第一反应是：不会又是个“民科”吧？
然而事情并没有这么简单。翻阅黄皓的履历我们会发现，他本科毕业于北大数学系，并在2012获得了UCLA的博士学位，现在他已经是美国埃默里大学数学与计算机科学系的助理教授。



黄皓是真的解决了问题。他给出两页证明过程，只需要本科的知识就足以理解。数学界的同行们在拜读过后，无不被他大道至简的智慧所折服。
我们量子位将以尽量通俗的方式还原证明过程，与你一起解决这个跨世纪难题——布尔函数敏感度猜想（Boolean function sensitivity conjecture）。
首先，让我们先从布尔函数说起。
布尔函数
（以下是布尔函数的解释，熟悉编程的同学可以直接跳到第二部分。）
我们知道，数字电路都由逻辑门的组合实现任意功能，最常见的两种逻辑门是与门和或门。

与门（AND）只有在输入全是1的时候，才会输出1，否则输出0。
或门（OR）只要有一个输入是1，输出就是1，只有当输入全是0的时候，输出才是0。

同样在输入是(1,1)的情况下，与门会非常敏感，只要其中一个输入发生变化，结果就会变成0。而或门只有两个输入全部发生变化的时候，结果才会变为0。
与门和或门只有两个bit的输入，是最简单的情形。当有n个输入bit输入的时候，情形就变得复杂起来。
举一个日常的例子，当你攒了多年的钱终于凑足首付后，要去银行申请购房贷款。
银行柜员给了你一张表，里面有很多很多问题，你只能回答是或否。最终你填写的内容被一套复杂的过程处理，却得出不能贷款给你的结论。
这套处理过程的输入是布尔变量（是或否），输出也是布尔变量（是否批准贷款），因此是一个布尔函数。
事后的你再回想起来，觉得可以把某些问题的回答反过来，也许还能通过申请。最终你发现需要改掉超过7个问题，才能改变审批的结果。
那么我们就说，这个布尔函数在你最初答案的条件下敏感度是7。

对于一个布尔函数f，在某个输入x（x是n个bit的布尔变量）的情况下，有超过s个布尔变量变化时，结果才会反转。我们就说布尔函数f在输入为x时的敏感度为s(f,x)。
所有敏感度s(f,x)的最大值s叫做布尔函数f的敏感度。

1989年，Nisan和Szegedy两位猜测，s是关于n的一个多项式。这便是布尔函数敏感度猜想（Boolean function sensitivity conjecture）。
布尔函数敏感度猜想出现以来，就一直是计算机科学理论中最令人头疼的开放性问题之一。解决了它就解决了逻辑电路、算法上的很多理论问题，比如我们熟知的n位二进制信号的奇偶校验。
变成几何游戏
但是想直接证明布尔函数敏感度猜想实在太难了。好在1992年有两位数学家Gotsman和Linial巧妙地把它变成了一个通俗的几何游戏。
他们把数字电路中的n比特转化为n维空间中立方体的顶点。
比如一个2比特的输入总共有4种可能性：00、01、10、11。相当于正方形的四个顶点：(0,0)、(0,1)、(1,0)、(1,1)。正方形就是二维空间中立方体。




同样的，如果是3比特，就对应三维立方体的8个顶点，以此类推到更高的维度。




在立方体中，相邻的两个顶点只有一个坐标值有差异，分别为0和1，其他坐标值则完全相同。
因此，从立方体中的一个顶点移到它的相邻顶点，就相当于把布尔函数输入中的某个比特进行翻转。（妙啊！）
既然布尔函数的输入可以用顶点坐标来表示，那么输出呢？我们可以用两种颜色来定义。
比如用红色表示0，蓝色表示1。如果某个顶点是红色，意味着顶点三个坐标值组成的3比特输入布尔函数后会得到0。
举个例子：




在上图的那个布尔函数中，若输入是(0,1,1)，输出将会是1。
倘若我们把第一位翻转，好在布尔函数对这个变化并不敏感，输出仍然是1，在图中相当于把顶点移到了它的右边，颜色还是蓝色。
然而第三位翻转后，布尔函数对这个变化是敏感的，输出变为0，相当于把顶点移到了它的下边，颜色从蓝色变成红色。
如果在某种情况下，输入结果的任何一位发生翻转，输出结果都会从1变成0，那也就意味着这个蓝点周围都是红点，这个点的敏感度就是0，没有蓝点与它直接相连。
一个点周围与它同色的点的数量，等于布尔函数在这个顶点的敏感度。布尔函数的敏感度就是所有顶点敏感度中的最大值。

于是布尔函数敏感度猜想可以简化为N维立方体上的简单问题：

如果将n维立方体的超过一半的顶点染成红色，其余染成蓝色，是否总有一些红点有同色的邻居？如果有，周围红点的数量最多是多少？

Gotsman和Linial两位的原话是这样的：

设S是n维布尔超立方体{0,1} n任意子集，其大小为2n-1+1。那么在S中必然存在一个点，在S中至少有nc个邻居。（2n-1+1恰好比n维立方体的总顶点数一半多1个。）

其中c是一个介于0和1之间的常数，后面我们可以看到c=1/2。
如果被染成红色的顶点恰好等于总顶点数的一半。它们可能互不相邻。在三维立方体中就能找到一个例子：四个点（0,0,0），（1,1,0），（1,0,1）和（0,1,1）恰好都斜跨对角线。（下图中的红点）





但是，只要哪怕多增加一个点涂成红色，红点之间就必须出现连接。
灵感突发
即使布尔函数敏感度猜想已经在27年前已经被简化，但是这个问题还是被继续搁置了20多年。
直到7年前，当时博士刚刚毕业的黄皓，和新泽西州立大学的数学教授Michael Saks一起吃饭，听对方聊到这个猜想。
黄皓默默地把这个问题加到了自己的“任务清单”里。

借助柯西

为了解决这个问题，黄皓想到使用一个200年前的数学定理：柯西交错定理（Cauchy interlace theorem）。
这个定理将矩阵与它的子矩阵的特征值联系起来，使其成为研究高低维立方体之间关系的完美工具。二维立方体(正方形)是三维立方体的一个面，因此是后者的一个子集。
柯西交错定理的表述如下：

A是一个n×n阶矩阵，B是A的m×m阶主子矩阵(m<n)。矩阵A的特征值为λ1 ≥ λ2 ≥ ̈ ̈ ̈ ≥λn，矩阵B的特征值为μ1 ≥ μ2 ≥ ̈ ̈ ̈ ≥μm，那么：

已经接近答案了，还差点什么呢？可能是钱吧。
黄皓决定申请美国国家科学基金会拨款，进一步研究探讨这一问题。
就在上个月，黄皓坐在马德里的一家酒店里，写他的科研基金申请书时，突然灵感迸发：可以改变矩阵中某些数字的符号，推动证明过程，直至得出结果。
他构造了一组2n×2n阶矩阵，定义为：

可以很容易用数学归纳法证明：

根据矩阵特征值的定义，An的特征值只能是√n 和-√n 。
而An的对角元素全部是0，因此矩阵的迹Tr(An)=0。我们知道矩阵的迹等于所有特征值之和，所以√n 和-√n 的数量必须相等，都是2n-1个。

相邻矩阵

如果H是一个有m个顶点的图（由点和它们之间连线组成的图形），A是一个对称矩阵，并且A是图H的相邻矩阵。
所谓相邻矩阵，是指A的第u行第v列元素表示H的第u个点和第v个点是否相邻，如果不相邻，这个元素就等于0；如果相邻，这个元素就是-1或者1；此外对角元素必须等于0。
容易验证，前面我们构造的矩阵An就是n维立方体Qn的相邻矩阵。
假设图H是n维立方体的一部分（准确地说，叫做立方体Qn的诱导子图），那么H的相邻矩阵是An的一个主子矩阵。
假设λ1是矩阵A的最大本征值，v是λ1对应的本征向量，v1是本征向量v里绝对值最大的一个分量。

上面推导过程中第一个不等号成立的原因是和的绝对值小于绝对值的和。

第二个不等号也很简单：∆(H)是图H的敏感度，而左边是某个点的敏感度，图的敏感度是其所有点敏感度的最大值。
所以∆(H)≥|λ1|，即图H的敏感度∆(H)大于矩阵A的最大本征值的绝对值。
A是An的子矩阵。倘若H包含2n-1+1个顶点，带入到柯西交错定理中：




前面已经证明∆(H)≥|λ1|，所以∆(H)≥√n，而∆(H)就是n个bit布尔函数的敏感度。
证明完毕！
通过这种简单的方式，黄皓证明了：在n维立方体中超过一半点的任何子集中，总会有一些点连接到至少√n 个其他同色的点，从这个结果中可以立即得出敏感度猜想。
尾巴

“我希望黄皓今年秋天能够在硕士的组合数学课程讲授（证明过程），只要一节课就够了。”

法国国家科研中心的Clarie Mathieu看到了黄皓的证明时，不禁感叹证明过程的简单。
黄皓的结果甚至超过了证明灵敏度猜想所必需的结果，应该还会产生关于复杂性度量的新见解。比如用于n位二进制字符串的奇偶校验算法。
“它增加了我们的工具包，可以帮助回答布尔函数分析中的其他问题，”哥伦比亚大学计算机科学教授Servedio说，“我认为很多人在听到这个消息之后会在那个晚上睡得更轻松。”
不知道是什么让黄皓突然产生了灵感，但是有位网友说出了一种可能性：写科研基金申请或许真的能帮助科研吧（笑）。
关于黄皓




黄皓2007年从北京大学数学系毕业，赴加州大学洛杉矶分校深造，于2012年获得数学系博士学位，并获得当年的学位论文奖学金。
他毕业后在普林斯顿大学高等研究院、明尼苏达大学数学研究所从事博士后研究工作，之后进入埃默里大学数学系，担任助理教授，先后在Journal of Combinatorial Theory等学术期刊上发表过21篇学术论文。
黄皓的主要研究方向是极值与概率组合、结构图论、理论计算机科学。
传送门
论文链接：
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
https://arxiv.org/abs/1907.00847
— 完 —
诚挚招聘
量子位正在招募编辑/记者，工作地点在北京中关村。期待有才气、有热情的同学加入我们！相关细节，请在量子位公众号(QbitAI)对话界面，回复“招聘”两个字。
量子位 QbitAI · 头条号签约作者
վ'ᴗ' ի 追踪AI技术和产品新动态

我知道答案 本帖寻求最佳答案回答被采纳后将获得系统奖励10 天空金币 , 目前已有1人回答

林子大了，什么鸟都有了啊！