数学家提出敏感性猜想的证明

近三十年来，敏感性猜想一直是理论计算机科学中最重要、最令人困惑的悬而未决的问题之一。通过埃默里大学数学助理教授黄浩的工作，它似乎终于遇到了对手。

Huang 将在 7 月 15 日至 19 日于瑞士苏黎世举行的随机结构和算法国际会议上展示敏感性猜想的证明。

“自 2012 年以来，我一直在解决这个问题，”黄说，“但大约一周前，我想到了关键的想法。我终于找到了解决它的正确工具。”

黄在他的主页上发布了这个证明，很快在社交媒体上的数学家和计算机科学家中引起了轰动，他们称赞其非凡的简洁性和简单性。

敏感性猜想与布尔数据相关，它将信息映射为真假或 1-0 二进制。布尔函数在复杂性理论以及数字计算机的电路和芯片设计中发挥着重要作用。

Huang解释说：“在数学中，布尔函数是最基本的离散主题之一，就像数字，图形或几何形状一样。”

布尔函数有许多复杂性度量，并且几乎所有度量——包括决策树复杂性、证书复杂性、随机查询复杂性和许多其他——都已知是多项式相关的。然而，有一种未知的情况，即所谓的布尔函数的敏感性，它衡量的是一次改变一个输入时函数的敏感性。

1994年，数学家Noam Nisan和Mario Szegedy针对这个未知案例提出了敏感性猜想。

“他们的猜想表明布尔函数的敏感性也与其他度量呈多项式相关，”黄说。“如果是真的，那么它就不再是一个异常值，它会加入其他人的行列。”

黄开发了一种代数方法来证明这个猜想。“我希望这种方法也有可能应用于其他对计算机科学很重要的组合和复杂性问题，”他说。