华人学者解开计较机规模30年困难：布尔函数敏感度意料

克日，美国艾默里大学计较机与数学科学系传授黄皓（Hao Huang）用一篇短短 6 页的论文「轻松」证明白困扰理论计较机规模数十年的布尔函数敏感度意料，激发了计较机和数学规模社区的普及存眷。布尔函数敏感度意料是理论计较机科学中近三十年来最重要，最令人狐疑的开放性题目之一。

论文长度仅有 6 页，其焦点证明内容只有两页，不外黄皓为了办理这个题目耗费了 7 年时刻的思索。

本月初，一篇仅有 6 页的论文暗暗登上了 arXiv，随之而来的是学界的惊动。这篇由华人学者黄皓所著的研究办理了困扰计较机科学规模的困难：布尔函数的敏感度意料（sensitivity conjecture），而这篇论文中现实的证明部门只有两页纸。

完成这一壮举的数学家宦珐来自广东汕头，他 2007 年本科结业于北京大学，博士就读于加州大学洛杉矶分校（UCLA），师从闻名数学家 Benny Sudakov 传授。黄皓于 2012 年得到博士学位，2012-2014 年受邀会见普林斯顿高档研究院，现接受美国艾默里大学数学系助理传授。其首要研究规模包罗极值组合、图论及理论计较机。已经在 JCTB、JCTA、Combinatorica、SIAM J. Discrete Math 等国际闻名期刊上颁发及接管颁发论文 20 余篇。

布尔函数的敏感度意料首要涉及计较机电路的基本结构块布局，迄今已快 30 年。在这二十余年中，该意料难倒了很多优越的计较机科学家，而黄皓提出的证明要领简朴到可以用一篇推文总结：

CMU 计较机科学系传授 Ryan O'Donnell 发推归纳综合了这篇证明。（图源：https://twitter.com/BooleanAnalysis/status/1145837576487612416）

行使有 200 年汗青的要领办理了 30 年汗青的重量级意料，有关布尔函数敏感度的证明让我们感觉到了数学之美。人们对付黄皓的论证纷纷暗示叹息：「这是我们看到过最瑰丽的两页证明。」

敏感度意料涉及布尔函数，布尔函数描写怎样基于对布尔输入的某种逻辑计较确定布尔值输出，在伟大性理论的题目和数字计较机的芯片计划中饰演基本脚色。

图源：http://jandan.net/2019/07/13/sensitivity-conjecture.html

这一意料可以简朴表述为：存在一个多项式 P，对全部的布尔函数 f，都创立 bs(f)≤P[s(f)]！

敏感度意料

法国国度科学研究中心 Claire Mathieu 用活跃的例子先容了布尔函数及其敏感度。

当你在银行贷款申请书上填写一系列 yes/no 题目的时辰，填写完之后，银行事恋职员将对你的填写功效举办评分，然后奉告你是否切合贷款前提。这一进程就是一个布尔函数：你的谜底是输入 bit，银行事恋职员的决定是输出 bit。

假如你的申请被拒，你也许会认为假如在答复某一个题目时说谎是否就可以改变最后的功效，好比在你现实上挣钱数目不高出 5 万美元时却暗示高出这一数量。假如该谎话可以或许改变最终决定功效，那么这一布尔函数就对特定 bit 的值「敏感」。若是有七个差异的谎话每一个都可以导致最终决定功效反转，那么这一布尔函数的敏感度就为 7。

计较机科学家将该布尔函数的敏感度界说为：当查察全部差异贷款资料时所获得的最大敏感度值。某种水平上，它可以计较在迷糊其词的环境下几多题目是真正重要的，这些环境包罗只要轻微改变即可环境反转的申请。

敏感度凡是是最轻易计较的伟大度怀抱指标，可是它并非独一富有开导性的指标。譬喻，银行事恋职员不让你填写纸质申请，而是举办面谈，先问简朴的题目，再按照你的答复举办后续的提问。这时辰银行人员在举办决定前必要提问的最大题目数目就是布尔函数的查询伟大度（query complexity）。

这一怀抱指标在许多场景下城市呈现，譬喻大夫在得出诊断功效之前想让病人尽也许少地举办搜查，可能呆板进修专家想让算法在举办物体分类之前尽也许少地查察物体的特性。「在大量场景中，如诊断场景或进修场景，底层法则的 query 伟大度低长短常值得信用的。」O'Donnell 暗示。

其他怀抱包罗探求将布尔函数写为数学表达式的最简朴要领，可能说计较银行人员应向上司展示几多个谜底，才气证明他们做了正确的贷款抉择。这里乃至尚有量子物理版本的查询伟大度，即银行人员可以在统一时刻扣问多个题目的「叠加」。找到这种怀抱与其他伟大度的相关，可以辅佐研究职员相识量子算法的范围性。

除了敏感度之外，计较机科学家已经证明白全部这些怀抱都是细密关联的。详细而言，它们之间存在多项式相关——譬喻一个怀抱也许大抵是另一个怀抱的平方或立方或平方根。

只有敏感度坚强地拒绝顺应这种简捷的暗示。许多研究职员猜疑敏感度与其他怀抱之间也存在多项式相关，但人们一向无法证明晰实不存在怪异的布尔函数，其敏感度与其他怀抱具有指数而非多项式相关。这意味着敏感度怀抱远小于其他怀抱。

「这一题目已经困扰了人们三十年。」德克萨斯大学奥斯汀分校计较机科学传授 Scott Aaronson 说道。

探求解法

黄皓在 2012 年尾与普林斯顿高档研究院数学家 Michael Saks 共进午餐的时辰听闻了敏感度意料，彼时前者照旧一名博士后。他当即被这一意料的简捷和优雅所吸引了。「从那一刻起，我就开始入神于思索这个题目了。」黄皓说道。

黄皓将敏感度意料插手了他感乐趣题目的「奥秘清单」中，每当他进修新的数学器材时，他城市思索这些要领是否会对办理敏感度意料有所辅佐。「每次我颁发新的论文之后，我总会回过甚来看看这个题目，」黄皓暗示。「虽然，我也常常在研究一番之后选择放弃，然后回到更为实际的题目上来。」

数学家宦珐在里斯本。

黄皓大白，正如研究社区广泛以为的一样，假如数学家可以证明一个有关差异维度立方体上点荟萃的意料，那么敏感度意料就可以获得办理。从一个 n 个 0 和 1 构成的序列到 n 维立方体上的点有一种天然的要领：只需行使 n 个 bit 作为点的坐标。

譬喻，有四个两位字符串 00、01、10 和 11，别离对应二维平面中正方形的四个角：(0,0)、(0,1)、(1,0) 和 (1,1)。同样，八个三位字符串别离对应三维立方体的八个角……以此类推。布尔函数可以被以为，用两种差异颜色为这些角举办着色的法则（好比为 0 涂赤色，1 涂上蓝色）。

1992 年，现任新泽西理工计较机学院院长 Craig Gotsman 和希伯来大学计较机科学传授 Nati Linial 找出了证明敏感度意料的思绪：通过答复一个有关差异维度立方体的题目将敏感度意料大大简化，假如你选择将高出一半的立方体尖角同时涂为赤色，是否老是有一些赤色点是与其他赤色点相毗连？（在这里，「毗连」暗示通过立方体的边相连，而不是通过任何对角线。）

假如你选择恰恰一半的立方体尖角，则很也许赤色点并不会相毗连。譬喻，在三维立方体的八个角中，(0,0,0), (1,1,0), (1,0,1) 和 (0,1,1) 这四个点只是通过对角线相连。可是只要立方体中高出一半的点被涂成赤色，那么必定会呈现相毗连的赤色点。题目在于：这些毗连是怎样漫衍的？是否存在一个高度毗连的点？

2013 年，黄皓以为领略这一题目的最佳路径是，行使矩阵暗示收集（矩阵可以追踪相连的点），并检测矩阵特性值。之后五年，他一向试验这个思绪，但都没有乐成。

2018 年，黄皓抉择行使柯西交织定理（Cauchy interlace theorem），该定理将矩阵特性值和子矩阵特性值关联起来，因此成为研究立方体及其尖角子集的美满器材。黄皓抉择向美国国度科学基金会提交申请，以进一步试探这一思绪。

随后在上个月，当他坐在马德里的一家旅店中撰写申请陈诉时，他溘然意识到本身可以通过简朴地改变矩阵中一些数字的标记来直接办理题目。通过这种方法，他可以证明在 n 维立方体中高出一半点的任何荟萃中，会有一些点和其他点有至少√n 个毗连，敏感度意料题目的证明就从这里开始。

当黄皓的论文进入 Claire Mathieu 的收件箱时，她的第一回响是「哦——哇」，她说道：「当一个题目已经存在了 30 年，而每小我私人都已经听闻过的时辰，我们天然以为证明它的要了解看起来冗长而伟大，可能很是高妙。」她打开论文并等候看到无法领略的内容。

可是，对付 Mathieu 和其他许多研究者来说，这一证明很是简朴，可以一次消化。「我但愿在本年的秋日在每个硕士级此外组合数学课程中教学这一内容——一堂课就够了。」Mathieu 暗示。

黄皓的研究功效乃至高出了证明敏感度意料所需的须要水平，其推理应该可以形成有关伟大度怀抱的新看法。「它充分了我们的器材库，让我们可以试图答复布尔函数说明中的其他题目。」哥伦比亚大学计较机科学传授 Rocco Servedio 说道。

虽然，更重要的是黄皓的功效让那些忧虑敏感度也许是伟大度怀抱天下中的异类的人安心了，Servedio 暗示。「我以为在这一证明推出往后，许多人终于能睡得着觉了。」

最后，这里是黄皓对布尔函数敏感度意料的两页纸证明：

更多详情拜见论文《Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture》（https://arxiv.org/pdf/1907.00847.pdf）。

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!