广告

一位数学家解决了困扰计算机科学家 30 年的问题

2019 年十大科学故事之 #28。

作者:Stephen Ornes
Google NewsGoogle News Preferred Source
数学家黄昊。图片来源:Kay Hinton/Emory University

新闻简报

注册我们的电子邮件新闻简报,获取最新的科学新闻

注册

7 月 1 日,埃默里大学数学家黄昊(Hao Huang)悄无声息地证明了一个定理——数学和计算机科学界因此而轰动。黄昊在短短六页的优美论证中,无可辩驳地证明了困扰计算机科学家数十年的“敏感性猜想”。

广告

这一证明点燃了数学界的讨论。“令人惊讶地简洁而优美,”耶路撒冷希伯来大学的数学家 Gil Kalai 在博客中写道。“这个证明表明,人们仍然可以找到解决深奥未解问题的简单方法,”圣达菲研究所的计算机科学家兼数学家 Cris Moore 说。

近 30 年来,许多思想家都曾试图解决这个难题。但直到黄昊出现之前,它一直是一个数学上的“痒点”,无人能挠——大家都知道问题所在,却无法触及。

该猜想与称为布尔函数的数学结构有关,布尔函数将多个二进制输入(例如 0 和 1,或“真”和“假”)转换为单个二进制输出。你可能会抛 10 次硬币,并定义一个布尔函数,如果在其中至少出现一次正面,则输出“1”,否则输出“0”。

这似乎很抽象,但布尔思想对于当今的技术格局至关重要,因为它们使得计算机能够进行计算。晶体管基本上是只有两种状态(开/关)的开关。但计算机科学家想更深入地了解这些函数的复杂性。例如:在函数的给定步骤中,你需要翻转多少个输入才能改变输出?这个问题的数值答案——然后大致扩展到整个函数——被称为敏感性。

敏感性是特殊的。衡量布尔函数复杂性的其他方法确实存在,但它们在数学上都被已知彼此相关。然而,敏感性一直是一个“特例”。敏感性猜想基本上描述了这种度量如何融入这个数学家族。人们认为它应该被包含在内,但实际证明它为何属于这个家族却是一个更棘手的问题。

黄昊说,该问题“欺骗性的简单性”在 2012 年首次引起了他的兴趣。“每次我决定重新拾起它时,都会花上三四天,一无所获,”他说。“这是我处理许多问题的方式。”他认为这些年来他在这上面花费了数百小时。

黄昊的突破发生在去年六月一个闷热的夜晚,当时他正在马德里的一个酒店房间里,与噪音很大的空调为伴。他本应该忙于完成一份棘手的资助申请,但却再次思考起敏感性问题。和之前的许多数学家一样,他认为处理布尔函数的二进制输入最自然的方式是将它们视为坐标点,也就是一个想象中的高维立方体的顶点。二十七年前,一位数学家和一位计算机科学家证明,如果你取这些点中至少一半的点集,并找到它们之间的联系,你就可以证明敏感性猜想。黄昊正是这么做的:他利用线性代数的工具证明了 1992 年的这个论断。之后,他写下了他的工作,并将其发布到网上,专家们对他的论证的无可辩驳性以及其紧凑、优雅的结构都同样感到赞叹。

黄昊并不惊讶一个数学家能够攻克这个计算机科学问题。“理论计算机科学本身就是抽象数学,”他说,这个问题恰恰证明了它们之间的联系。“计算机科学家经常需要问题具有应用性,但对我们数学家来说,我们更关心优雅,以及问题是否能被漂亮地表述出来。”

保持好奇

加入我们的列表

订阅我们的每周科学更新

查看我们的 隐私政策

订阅杂志

订阅可享封面价高达六折优惠 《发现》杂志。

订阅
广告

1篇免费文章