黄皓证明了计算机和数学中的难题: 敏感度猜想

最后编辑于 2019年08月05日 科技

黄皓,即Hao Huang,广东汕头人。他在2007年本科毕业于北京大学数学科学学院,之后奔赴加州大学洛杉矶分校数学系就读,并在2012年获得数学系的博士学位。他的研究领域包括极值组合学、概率与代数方法、谱图理论、结构图论和理论计算机科学等。黄皓现在是亚特兰大埃默里大学(Emory University)数学与计算机科学系的终身助理教授。


Image credit: Hao Huang and Emory University

值得一说的是,北京大学数学科学学院是一个非常牛*的基础科学型的学院,不管你是数学奥赛获奖者,还是另类数学天才,很多都希望进入这个中国排名第一的数学学院进行深造。

再来说说什么是敏感度猜想(Sensitivity Conjecture)。

在数学中,布尔函数总是有N个输入(每个输入都是0或1,总共有N个)、1个输出,也就是说输入是布尔值、输出也是布尔值。通俗来说,在确定有多个输入值的情况下(小于等于N),改变其中的几个输入值(会有不同组合的改变),会导致输出也发生改变,则改变的输入值的个数的最大值,就叫做这个布尔函数的敏感度。

那么,布尔函数的敏感度,和布尔函数的N个输入的N有关系吗?

1989年,以色列耶路撒冷希伯来大学的Noam Nisan和当时在美国芝加哥大学的Mario Szegedy,就提出了一个猜想,认为布尔函数的灵敏度和程度是和多项式相关的,也就是和N有关系,只是无法证明。

从该猜想提出之后,很多数学家和计算机科学家都尝试过证明,但都铩羽而归,知道黄皓出现。黄皓的证明只用了两页纸,不过我看两页纸的干货只需一页纸就行:诱导超立方体的子图和灵敏度猜想的证明(Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture)。

黄皓的证明很简洁,数学家们也不吝赞美,纷纷称赞这个证明完美、愉悦。这让我想起了石墨烯超导角度的发现者曹原,都是少年天才。

原文如下,大家也愉悦一下吧!

黄皓证明论文及PDF文件:
https://arxiv.org/abs/1907.00847
https://arxiv.org/pdf/1907.00847.pdf

黄皓个人介绍:
http://www.mathcs.emory.edu/~hhuan30/

登录注册后才能评论。