最近，美国埃默里大学计算机科学与数学教授黄浩用一篇简短的六页“简易”文章来证明布尔函数的敏感性猜想，这种猜想一直困扰着理论计算领域。几十年。并得到了数学界的广泛关注。布尔函数灵敏度的猜想是过去三十年中理论计算科学中最重要和最令人困惑的开放问题之一。
本月早些时候，一篇只有6页的文章进入了arXiv，随后在学术界引起轰动。中国学者黄伟的这项研究解决了困扰计算机科学领域的问题：布尔函数灵敏度的猜想，本文的实际测试部分只有两页。
完成这一壮举的数学家黄伟来自广东汕头，2007年毕业于北京大学，获得加州大学洛杉矶分校（UCLA）博士学位，并在那里与着名数学家Benny Sudakov一起学习。黄伟于2012年获得博士学位，并于2012 - 2014年应邀访问普林斯顿高等研究院。他目前是埃默里大学的数学助理教授。他的主要研究领域包括极值，图论和理论计算机的组合。他在国际知名期刊上发表并接受了20多篇文章，如JCTB，JCTA，Combinatorica和SIAM J. Discrete Math。
布尔函数的灵敏度假设主要涉及计算机电路块的基本结构，这种结构已有近30年的历史。在这二十年中，这个猜想困扰了许多优秀的计算机科学家，黄伟提出的测试方法非常简单，可以用推文总结：
七年思考，两页表明中国学者解决了计算机领域30年的问题：布尔函数的灵敏度猜想
使用一种有200年历史的方法来解决重量级猜想的30年历史，对布尔函数灵敏度的测试使我们感受到数学的美。人们已经对黄的论点表示了感叹：“这是我们见过的最美丽的两页证明。”
七年思考，两页表明中国学者解决了计算机领域30年的问题：布尔函数的灵敏度猜想
灵敏度猜想涉及布尔函数，它描述了如何根据布尔输入的某种逻辑计算确定布尔输出，在数字计算机的复杂性理论和芯片设计问题中发挥了基础作用。
七年思考，两页表明中国学者解决了计算机领域30年的问题：布尔函数的灵敏度猜想
法国国家科学研究中心的Claire Mathieu用生动的例子介绍了布尔函数及其灵敏度。当您在银行贷款申请中完成一系列是/否问题后，银行工作人员会在完成后评估您的结果，并告诉您是否有资格获得贷款。这个过程是一个布尔函数：你的答案是输入位，银行职员的决定是输出位。
如果您的请求被拒绝，您可能会觉得如果您在回答问题时撒谎，您可能会更改最终结果。例如，如果您的收入低于50,000美元，您将超过该数字。如果谎言可以改变最终决定的结果，则布尔函数对特定位的值“敏感”。如果有七个不同的谎言，每个谎言都可能导致最终决定的反转，那么这个布尔函数的灵敏度为7。
计算机科学家将布尔函数的灵敏度定义为查看所有不同贷款材料时获得的最大灵敏度值。在某种程度上，您可以计算在模糊不清的情况下有多少问题非常重要，包括情况稍有变化的应用程序。
七年思考，两页表明中国学者解决了计算机领域30年的问题：布尔函数的灵敏度猜想
灵敏度通常是最容易计算的复杂度指标，但它不是唯一的照明指标。例如，银行工作人员不允许您填写纸质申请表，但会进行面试，先问您一个简单的问题，然后跟进您的答案。此时，银行职员在做出决定之前必须提出的最大问题数是布尔函数咨询的复杂性。
该度量可以在许多场景中发生，例如希望患者在导出诊断之前尽可能少地进行验证的医生，或者机器学习专家希望算法在对对象进行分类之前尽可能少地查看对象的特征。 “在很多场景中，例如诊断或学习场景，底层规则查询的低复杂性是非常有益的，”O'Donnell说。
其他指标包括找到将布尔函数编写为数学表达式的最简单方法，或计算银行员工应向银行显示的响应数量，以表明他们做出了正确的贷款决策。在量子物理学版本中甚至存在复杂的咨询，银行工作人员可以同时请求多个问题的“叠加”。找到该度量与其他复杂性之间的关系可以帮助研究人员理解量子算法的局限性。
除敏感性外，计算机科学家还表明，所有这些指标都密切相关。具体而言，它们之间存在多项式关系。——例如，度量可以近似为另一个度量的平方或立方或平方根。
只有敏感才会顽固地拒绝适应这种简洁的表现形式。许多研究人员怀疑灵敏度与其他指标之间存在多项式关系，但不可能证明没有奇怪的布尔函数，其灵敏度与其他指标具有指数而非多项式关系。这意味着灵敏度指标远小于其他指标。“这个问题一直困扰着人们30年，”德克萨斯大学奥斯汀分校计算机科学教授Scott Aaronson说。
寻找解决方案
2012年底，黄伟与普林斯顿高等研究院的数学家迈克尔·萨克斯共进午餐时听到了一个敏感性猜想，其中第一位是博士后研究员。他立刻被这个猜想的简洁和优雅所吸引。 “从那一刻起，我开始考虑这个问题，”黄说。
黄伟将这种敏感性猜想添加到了感兴趣的“秘密清单”中。当您学习新的数学工具时，您将考虑这些方法是否有助于解决灵敏度猜想。 “每次我发表一篇新文章，我都会一直关注这个问题，”黄说。 “当然，我经常选择在研究后放弃，然后回归更现实的问题。”
七年思考，两页表明中国学者解决了计算机领域30年的问题：布尔函数的灵敏度猜想
数学家黄伟在里斯本。
黄伟明白，正如研究界普遍认为的那样，如果数学家可以证明对一组不同维度的立方点的推测，可以解决灵敏度猜想。有一种自然的方法可以从n 0和1的序列移动到n维立方体中的一个点：只使用n位作为点的坐标。
例如，有四个两位字符串00,01,10和11，它们对应于二维平面中正方形的四个角：（0,0），（0,1），（1,0）和（0） 1,1）。类似地，八个三位数字符串对应于三维立方体的八个角，依此类推。布尔函数可以被视为用两种不同颜色着色这些角的规则（例如，0表示红色，1表示蓝色）。
1992年，新泽西理工学院院长Craig Gotsman和希伯来大学计算机科学教授Nati Linial发现了测试灵敏度猜想的想法：通过响应a大大简化了灵敏度猜想。如果您愿意，可以询问不同尺寸的立方体。立方体的一半以上角落同时涂成红色。是否总有一些红点连接到其他红点？ （这里，“连接”意味着通过立方体的边缘连接，而不是通过任何对角线连接）。
如果您选择正好一半的立方角，则可能是红点未连接。例如，在三维立方体的八个角中，四个点（0,0,0），（1,1,0），（1,0,1）和（0,1,1）是正确的对角线的线是连接的。但是，当超过一半的立方体点被涂成红色时，连接的红点肯定会出现。问题是：这些连接是如何分配的？是否存在高度关联点？2013年，黄伟认为理解这个问题的最好方法是使用矩阵来表示网络（矩阵可以跟踪连接点）并检测矩阵自身的值。五年后，他一直在尝试这个想法，但没有成功。
在2018年，黄伟决定使用Cauchy交织定理，该定理将矩阵自身值与子矩阵自身值相关联，从而成为研究立方体及其尖锐子集的理想工具。黄伟决定向国家科学基金会提出要求，进一步探讨这一想法。
然后，上个月，当他在马德里的一家酒店写报告时，他突然意识到他可以通过简单地改变矩阵中某些数字的符号来直接解决问题。通过这种方式，您可以证明在任何超过一半的n维立方体中，有一些点与其他点之间至少有√n连接，并且此处开始出现灵敏度猜想问题的证据。
当黄伟的文章进入Claire Mathieu的收件箱时，她的第一反应是“哦，——哇，”他说。 “当一个问题存在了30年，每个人都听到了，当然，证明这个问题的方法似乎很长很复杂，或者非常先进。”他打开报纸，希望看到一些无法理解的东西。
然而，对于Mathieu和许多其他研究人员来说，这个测试非常简单，可以同时消化。 “我希望今年秋天在每个硕士级别的综合数学课程中教授这些内容.——一课就足够了，”Mathieu说。
黄琦研究的结果甚至超过了证明灵敏度猜想所必需的水平，推理必须形成关于复杂性度量的新知识。 “它丰富了我们的工具库，因此我们可以尝试回答布尔函数分析中的其他问题，”哥伦比亚大学计算机科学教授Rocco Servedio说。
当然，更重要的是，黄伟的结果让那些担心敏感度可能是复杂度指标世界异质性的人放心，Servedio说。 “我认为，在进行这项测试后，很多人终于可以睡觉了。
上海IT外包服务网 链接：http://www.linemore.com
中文
电话咨询
微信咨询
公众号
