1992年，耶路撒冷希伯来大学的Noam Nisan和罗格斯大学的Mario Szegedy提出布林函数 敏感度猜想。这成为了计算机科学近三十年来最重要的开放性问题之一。这个月，Emor y大学的华人教授黄皓用两页纸证明了此问题。 证明在连结p3,p4 http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf 电脑科学家发明了各种衡量布林函数复杂度的方法。布林函数的敏感度就是将某输入位 元反转後使得输出被反转的机会。而“查询复杂度”则是你需要确定多少个输入位元才 能定下输出位元。 每一种测度都以独特的视角审视布林函数的结构。电脑科学家们发现几乎所有测度都在 统一框架内互相相关，知道其中一个测量值让你可以估计其它测量值。而这其中唯一的 格格不入者正是敏感度。 想像你在向银行申请贷款，需要填一系列答案为是或否的问题。填完後银行人员会告诉 你是否批准贷款。这个过程就是一个布林函数，你的答案是输入位元，而银行人员的决 定是输出位元。 如果你的申请被拒，你也许会想在某个问题上撒谎来改变结果，例如年薪是否为5万以上 ，如果改变这个回答就能彻底反转最後的决定，电脑科学家称该布林函数对於这个特定 位元“敏感”。如果有7个问题的答案任一改一下都能改变结果，此布林函数的敏感度为 7。 电脑科学家把布林函数的敏感度定义为在所有可能的申请中最大的那个敏感度值。换句 话说，这个测度计算在最极端的情况下，有多少道问题是真正至关重要的？而最多需要 几个问题可以做出决定就是布林函数的查询复杂度。 除了敏感度以外，电脑科学家已经证明了所有测度值之间都成多项式关系。例如，一个 测度值可能大约是另一个测度值的平方，或立方，或平方根。只有敏感度尚未融入到这 个优美的框架之中。 黄皓在2012年从数学家Michael Saks听到了这个猜想。他立刻被这个猜想的简洁优美吸 引了。“自那一刻起，我不断固执地思索着这个问题。” 黄皓知道如果数学家能证明某个关於不同维度下方形顶点集合的简洁猜想，那麽敏感度 猜想就等於被证明了。n个输入位元0或1和n维方形顶点有一种自然的映射关系，它可以 被视为该顶点的座标。 举例而言，2位元串共有4种情况00, 01, 10和11，对应於二维平面上正方形的顶点(0,0), (0,1), (1,0)和(1,1)。同样，8个3位元串对应于三维立方的8个顶点，更高维下也以此 类推。布林函数等於把所有顶点涂上两种不同颜色的方法（例如输出为1涂蓝色，0涂红 色）。 2013年，黄皓认为证明的最佳思路为将网路转化为一个代表两点是否相连的矩阵，并探 索这个矩阵的特徵值。在接下来的5年里，他不断重温这个思路，但一直没有突破。“至 少思考这个问题经常让我很快入眠。” 2018年，黄皓突然意识到可以借用柯西交错定理。这个定理将矩阵的特徵值和其子矩阵 的特徵值挂勾，这意味着用该定理来研究方形和其顶点子集再恰当不过了。 黄皓决定向国家科学基金申请经费，当他坐在马德里的酒店里写申请书时，突发意识到 只要把矩阵里某些数的符号逆转就能把问题完全解决。这麽一来，他能证明n维方形中任 一超过一半顶点的集合中，必有一点和至少n个其它同在该集合中的点相连。敏感度猜想 终於被证明。 当同行评审Mathieu收到黄皓的论文时，她已经做好完全看不懂的准备。但是证明非常简 洁，Mathieu和其他同行一读完就理解了。她说：“我觉得今年秋天所有组合数学硕士课 程都可以教这个定理了，而且一节课就可以教完。” 黄皓简介: 出生於汕头，2003年凭藉优异的成绩被保送至北京大学攻读数学。黄皓在北 京大学举办数学建模与计算机应用竞赛中获得三等奖，并出现在北大数学百年学生名录 上。2007年毕业後，黄皓在美国加州大学洛杉矶分校读博，师从着名数学家Benny Suda kov教授，并於2012年获得学位。现担任Emory大学数学系助理教授。主要研究领域包括 极值组合、图论及计算机理论。 ※ 编辑: bulls0722 (42.72.69.32 台湾), 07/31/2019 15:02:00