“敏感度”假说使许多杰出的计算机科学家感到困惑，但是事实证明它的新证据是如此简单，以至于一位研究人员可以将其简化为一条推文
今年夏天发表的
工作结束了关于计算机电路基本构件结构的假设近30年的历史。 这种“敏感性”的假设困扰了许多杰出的计算机科学家多年，但事实证明它的新证据是如此简单，以至于一位研究人员可以将其简化为一条推文。
德克萨斯大学奥斯汀分校的
斯科特·亚伦森 （ Scott Aaronson）在他的博客中
写道： “这一假设是所有组合学和理论信息学领域最烦人，最可耻的开放式任务之一。” 他在一封电子邮件中补充说：“试图证明它但没有做到的人的名单是离散数学和理论计算机科学领域最杰出的人的名单。”
该假设与布尔函数（布尔函数）相关，布尔函数是将传入位（零和一）的字符串转换为单个位的规则。 当所有输入位均为1时，一个这样的规则将产生1，否则将产生0。 如果该行包含偶数个单位，则另一个规则返回0；在另一种情况下，则返回1。 哥伦比亚大学的
Rocco Cenedio说，每个计算机电路都是布尔函数的组合，这使它们成为“计算机科学中所有工作的基础材料”。
多年来，计算机科学中已经开发出许多方法来测量给定布尔函数的复杂性。 每个度量都使用其自己的方面，即输入线路信息如何确定输出位。 例如，布尔函数的“敏感性”可以粗略地说，表示更改输入中的单个位将更改输出中的位的概率。 “请求复杂度”计算需要请求多少个输入位，以便确定地知道输出将是什么。
每种度量在布尔函数的结构上都有其独特的观点。 但是，计算机科学家发现，几乎所有这些措施都适用于通用平台，并且通过一项措施的价值，一项措施可以大致判断另一项措施的重要性。 而且只有一种复杂性度量不适合此方案：敏感性。
1992年，来自耶路撒冷希伯来大学的Noam Nisan和现在在罗格斯大学（Rutgers University）工作的Mario Szeged建议，敏感性仍然适用于此平台。 但是没有人能证明这一点。 Cenedio说：“这个问题在研究布尔函数方面非常出色。”
卡耐基梅隆大学的赖安·奥多内尔说：“人们写了冗长而复杂的作品，试图取得很小的进步。”
现在，埃默里大学的数学家
黄浩借助一个精巧而又基本的，与立方体上的点的组合有关的两页证明，证明了灵敏度假设。 法国国家科学研究中心的克莱尔·马修（Claire Matthew）在接受Skype采访时写道：“它像一颗珍贵的珍珠一样美丽。”
Aaronson和O'Donnell称胡安（Juan）的工作为敏感性假设的“书”证明，是指帕尔德罗斯（PalErdös）的“天书”的概念，其中上帝写下了每个定理的理想证明。 “我很难想象，即使上帝也知道敏感性定理的更简单证明，”亚伦森写道。
敏感话题
马修说，想像一下，您正在填写一张表格，询问银行贷款申请表中的问题，答案可能是/否。 完成后，银行家将评估结果并告诉您是否适合贷款。 这个过程是布尔函数：您的答案是输入位，而银行家的决定是输出。
如果您的申请被拒绝，您可以考虑是否可以通过提出一个问题来更改结果-也许可以声明您每年的收入超过50,000美元，尽管事实并非如此。 如果这个谎言改变了考虑的结果，计算机科学家将称这种布尔函数对特定位的值“敏感”。 例如，如果您可能位于七个位置之一中，并且每次更改结果，那么布尔函数评估贷款申请的敏感性为7。
计算机科学家将布尔函数的整体灵敏度定义为填写应用程序的所有可能选项的最高灵敏度值。 从某种意义上说，此度量标准计算出在大多数临界情况下有多少个问题真正重要-在应用程序中，如果对应用程序本身进行稍加修改，其结果最容易更改。
为了可视化电路对由于位反转而引起的误差的敏感性，可以将n个输入位表示为n维立方体的顶点坐标。 如果路径产生1，则将顶点着色为蓝色；如果路径为0，则将着色为红色。
在左中角：带有输入011的简单布尔函数的输出可以由多维数据集（0,1,1）上方的蓝点表示。
居中：旋转第一位，我们将转到立方体的蓝色顶部（1,1,1）。 该功能对该位的反转不敏感。
在右中间：转到第三位，我们将转到多维数据集的红色顶部（0,1,0）。 该功能对该位的反转很敏感。
给多维数据集的所有顶点着色后，我们得到给定传入线的敏感位数等于相应顶点与另一种颜色的顶点之间的连接数。 环路灵敏度定义为任何输入线中敏感位的最大数量，因此此功能的灵敏度为2。灵敏度通常是计算复杂度最简单的方法之一，但它根本不是简单的解释性方法。 例如，我们的银行家可以从一个问题开始，而不是给您填写表格，然后使用您的答案来确定接下来要问的问题。 银行家在做出决定之前需要问的最大问题是请求布尔函数的复杂性。
这种措施在各种情况下都会出现-例如，医生可能希望让患者收集尽可能少的测试以进行诊断，或者机器学习专家可能希望创建一种算法来研究对象之前尽可能少的属性。他将能够正确地对其进行分类。 O'Donnell说：“在许多情况下-诊断或培训-您希望基本规则具有较低的查询复杂度。”
除其他措施外，还寻求最简单的方法来以数学表达式的形式编写布尔函数，或者计算银行家必须向老板显示的答案数量，以证明应用程序已正确处理。 当银行家同时询问几个问题的“叠加”时，甚至量子物理学中查询的复杂性也有所不同。 了解了该度量与其他复杂性度量之间的关系后，研究人员可以更好地理解量子算法的局限性。
计算机科学家已经证明，除了敏感性之外，所有这些度量之间都存在密切的关系。 更具体地说，他们发现它们通过多项式相关性相互关联-例如，一种度量可以表示为另一度量的平方或立方。 而且只有敏感性顽固地抵抗了，不想集成到这种方便的分类方案中。 许多研究人员怀疑它应该适用，但无法证明不存在奇怪的布尔函数，其敏感性与其他度量不是通过多项式而是通过指数相关性关联的，在这种情况下，这意味着敏感性度量从根本上讲是比其余的小。
“这个问题使人们醒了30年，”亚伦森说。
角落解决方案
Juan于2012年底与高等研究院的数学家
Michael Sachs一起吃晚饭时发现了这个假设。 该假设的简单和优雅使他立即着迷。 他说：“从那一刻起，我就对她产生了迷恋。”
胡安将敏感度假设添加到他感兴趣的问题的“秘密清单”中，当他发现一些新的数学工具时，他想知道是否可以帮助他。 他说：“每次出版另一本作品后，我都回到了这项任务。” “当然，我分配了时间和精力来完成更现实的任务。”
郝煌最近在里斯本度假像研究界中的许多人一样，胡安也知道，如果数学家可以用一个更简单的条件来证明另一种假设，那么关于假设的论点就可以得到证明。 从零和一串到n维立方体上的一个点，有一种自然的方法：只需使用n位作为该点的坐标即可。
例如，四条两位线-00、01、10和11-对应于二维平面上正方形的四个角：（0,0），（0,1），（1,0）和（1,1）。 类似地，对于更高的维度，八个三位字符串对应于三维立方体的八个角，依此类推，以此类推。 可以将布尔函数视为用两种不同颜色（例如，红色表示0，蓝色表示1）对这些立方角进行着色的规则。
1992年，现在在希伯来大学新泽西技术学院和Nati Lignal工作的
Craig Gotsman意识到，可以将灵敏度假设的证明简化为关于不同维度的多维数据集的简单问题的答案：如果您选择的任何集合都包含超过一半的多维数据集顶点，然后将它们着色为红色，是否有必要找到一个与许多其他红点连接的红点（通过“连接的”点，我们的意思是两个顶点通过一条公共边相连，而不是位于 对角线）。
如果我们的子集恰好包含立方体顶点的一半，则它们可能不会相互连接。 例如，三维立方体的八个角中有四个点，
（0,0,0），（1,1,0），（1,0,1）和（0,1,1）彼此对角放置。 但是，只要任何尺寸的立方体的一半以上的顶点变成红色，它们之间的红色点就必须相互连接。 问题是这些连接如何分布？ 这些峰中是否至少会有一个具有更多连接的峰？
在2013年，Juan开始认为了解此问题的最佳方法可能是使用一种标准方法来表示网络，该方法使用矩阵来跟踪连接的点，然后研究许多称为矩阵特征值的数字。 五年来，他定期回到这个想法，但无济于事。 他在亚伦森（Aaronson）的博客文章中评论说：“至少由于我在睡觉前对她的看法，使我更容易入睡许多晚上。”
然后在2018年，Juan考虑使用200年前的数学表达式Cauchy交替定理，将矩阵的特征值与子矩阵连接起来，这也许使其成为研究多维数据集与其顶点子集之间关系的理想工具。 胡安决定向国家科学基金会申请拨款，以进一步探索这一想法。
然后，上个月，他坐在马德里的一家旅馆里，填写了一份赠款申请书，突然意识到他可以将这种方法的使用扩展到最后，只需更改矩阵中某些数字的符号即可。 通过这种方式，他能够证明在n维立方体的一半以上的任意一组顶点中，将存在与至少√n个其他点相关联的点-灵敏度假设立即由该结果得出。
她说，当马修在邮件中收到胡安的工作时，她的第一个反应是“哎呀”。 “当一项任务已经存在30年并且每个人都知道它的时候，那么它的证明就必须是非常漫长而复杂的，或者非常深刻的。” 她打开了包含工作的文件，期望她什么都不懂。
但是，证明足够简单，因此Matthew和其他研究人员可以一次坐下来消化它。 她在Skype上写道：“我认为今年秋天，学生会在每门硕士课程的组合课程中作为一次讲座的一部分告诉他。”
事实证明，胡安的结果甚至比证明这一假设所必需的结果还要强大，而且这种力量应该为我们提供有关复杂性度量的新思路。 Cenedio说：“它已添加到我们的工具包中，可能有助于回答与布尔函数有关的其他问题。”
但最重要的是，胡安的研究结果使我们不必担心敏感度在复杂性测量领域是否是陌生的外星人。 “我认为当晚得知这些结果，很多人就可以安然入睡。”