33岁华人数学家花费7年，仅用2页纸就解决困扰科学界30年的难题

近日，理论计算机界以及数学界都为一个消息而兴奋，那就是困扰了大家近30年的布尔函数敏感度猜想终于被攻克，而将它斩落马下的就是33岁的华人数学家黄皓。

在数学中， 布尔函数（Boolean function）通常是用于描述如何基于对布尔输入的某种逻辑 计算确定布尔值输出，提出至今已有近200年的时间。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中。

布尔是指计算机科学中的逻辑数据类型，以发明布尔代数的数学家乔治·布尔为名。它是只有两种值的原始类型，通常是True和False。而布尔值则是“真” True 或“假” False 中的一个。在逻辑中，真值或逻辑值是指示一个陈述在什么程度上是真的。在计算机编程上多称作布尔值。动作脚本也会在适当时将值 True 和 False 转换为 1 和 0。

简单来说，布尔函数其实并不复杂，就是输入一段由0和1组成的比特串，输出是0或者1。（比特是计算机专业术语，是信息量单位，比特串就是比特组成的一串数字，而比特数中1个字节=8个比特）

组成计算机的电路实际上也是“True”“或”“False”逻辑电路的组合，多年来，计算机科学家已经开发出许多方法来测量给定布尔函数的复杂性。

经过科学家研究发现，关于布尔函数复杂性的度量措施都适用于一个统一的框架，但有一个复杂性指标似乎并不适用——“灵敏度”。

灵敏度（sensitivity conjecture）是一种衡量布尔函数复杂度的方法，它被定义为导致布尔函数翻转的最大比特数，通过捕获输入字符串中的信息来影响输出位的改变。举一个简单的例子，对于一个给定的n位比特串，每一位翻转一下（由1变成0或者由0变成1），如果布尔函数的值也发生翻转，那这个位就算一次，最后可以得到有多少个位翻转会改变函数值。这个叫做局部的敏感度。整体的敏感度就是对于所有的n位比特串，取最大的一个局部敏感度。

换句话说，布尔函数的“灵敏度”跟踪翻转单个输入位改变输出位的可能性。不过敏感度这个很基本的度量——大家不知道它的位置，虽然一直猜测它是属于这个统一的框架的，但没人能给出证明。

理论计算机界的重大难题

1992年，耶路撒冷希伯来大学的Noam Nisan和现在罗格斯大学的Mario Szegedy 提出了理论计算机界重要的猜想——布尔函数敏感度猜想，敏感度猜想指出：“灵敏度”的确适合这一框架。 用公式表示就是：

存在一个多项式P，对所有的布尔函数f，都成立 bs（f）≤P[s（f）]！

这成为了理论计算机科学近三十年来最重要、最令人困惑的开放性问题之一，但是几十年来一直没有人能够解决它。

而且最重要的是灵敏度猜想的证明具有很大的实践意义，主要涉及计算机电路的基础构造块结构。

外媒Quantamagazine就此问题举例说：如果你向银行申请贷款，那么就需要填一系列答案为是或否的问题，银行再根据你的答案进行评分做出决定——这个过程就是一个布尔函数，你的答案就是输入比特，银行的决定就是输出比特。如果你改变某个问题的答案会导致结果翻转，这个比特/答案就被定义为敏感了，如果有7个问题任意一个翻转会导致结果翻转，那么其敏感度就是7。

那么如果解决了这个问题，银行家可以向老板展示尽量少的答案以证明他们已做出正确的贷款决策，也可以更快地判定你的贷款需求是否合理。当然，这只是一个简单的小例子，它的实践范围可谓非常广泛。

数学界称呼布尔函数敏感度猜想为：“组合论和理论计算机科学中最令人沮丧和难堪的问题之一，试图解决它而失败的人们就是离散数学和理论计算机科学的名人堂”。由此可见这个问题的难度以及重要性。

而解决这个难题的33岁小伙黄皓，他在这个问题上的证明过程可以说让所有数学家惊叹。

黄皓出生于广东汕头，17岁被保送到北大数学系，在北大就读时，黄皓就在北京大学举办的首届“江泽涵”杯数学建模与计算机应用竞赛中获得三等奖，并出现在北大数学百年学生名录上。

后来黄皓在美国加州大学洛杉矶分校读博，师从国际著名数学家Benny Sudakov教授，他主要研究的方向是极值组合、图论及计算机理论。图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

2012年末，在受访美国普林斯顿高等研究院期间，黄皓无意间听说了敏感性猜想，、他立刻被这个猜想的简洁和优雅所吸引，由此开始了长达7年的攻坚之路。

黄皓认为从n 个0和1 的字符串到n维立方体上的点有一种自然的映射关系。那么就可以将敏感度猜想的证明归结为解答关于不同维度下的立方体的简单问题。这样就把问题转化到自己最擅长的图论上来了。

图源网络，对敏感度猜想的详细简介，这是讲诉了字符串和N维立体之间的转化关系

黄皓试图通过通过标准网络来表示网络，该矩阵跟踪哪些点连接，然后检查一组称为矩阵特征值的数字。却一直没有成功。

后来黄皓在研究柯西交错定理的时候发现，它能将矩阵的特征值与子矩阵的特征值联系起来，使其成为研究立方体与立方体之间关系的完美工具。

而到了2019年，他突然意识到他可以通过改变他的矩阵中某些数字的符号来推动这种方法的完成。通过这种方式，他能够证明在n维立方体中超过一半点的任何子集中，总会有一些点连接到至少√n 个其他同色的点，从这个结果中可以立即得出敏感度猜想。

n维立方体

而这个黄皓整整思考了7年的数学界难题，核心证明过程却只需要2张纸，它的证明过程甚至可以用四行来概括。

Ex.1: edge-signing of n-cube with 2^{n-1} eigs each of +/-sqrt(n)

Interlacing=>Any induced subgraph with >2^{n-1} vtcs has max eig >= sqrt(n)

Ex.2: In subgraph, max eig <= max valency, even with signs

Hence [GL92] the Sensitivity Conj, s(f) >= sqrt(deg(f)

如果用一句概括，那就是黄皓证明了bs（f）≤P[s（f）]。

在这篇核心证明过程只有2页的论文中，黄皓先证明n维超立方图的生成子图的相关命题，将猜想作为命题的直接推论。其精巧思路和简单明了的过程，在社交媒体上赢得了计算机科学家和数学家的一片赞誉。

论文首页

而这篇论文的价值还不止于此，黄皓还开发了一种新的代数方法，他说：“我希望这种方法也有可能应用到对计算机科学的发展至关重要的其他组合和复杂性问题上”。

总体来说，黄皓的结果甚至超过了证明灵敏度猜想所必需的结果，这种发现应该会产生关于复杂性度量的新见解。

尽管如此，黄的结果仍然令人担心，在复杂的世界中，敏感性是否可能是一些奇怪的异常值，还需要后续进一步的研究。

但不管怎么样，困扰数学界30年的难题被他给破解，而且其中诞生的新的数学方法、数学工具、数学思路都是献给数学界最大的财富！比如黄皓的证明工作刚刚完成，许多数学家就已经跃跃欲试，斯坦福大学教授高德纳甚至尝试将黄皓的证明简化到了一页。