这位数学家的“神秘”新方法解决了一个30年前的问题

 一位数学家解决了数学与计算机科学之间30年的问题。他使用了一种创新,优雅的证据,让他的同事们惊叹于它的简洁。

QQ截图20190731212124.jpg

亚特兰大埃默里大学数学助理教授黄浩证明了一种称为灵敏度猜想的数学概念,它以极其粗略的术语说明了你可以在不改变输出的情况下将输入改变为多少(这个是它的敏感性)。

自数学家首次提出灵敏度猜想(未经证明)以来的几十年中,理论计算机科学家意识到它对确定最有效的信息处理方法具有重大意义。

根据该领域的其他专家的说法,黄的证明有什么值得注意的,不仅仅是因为黄某将其拉下来,而且还有他所做的那种优雅而直截了当的方式。他的证据尚未经过正式的同行评审或在任何数学期刊上发表。但在黄先生于7月1日在网上发布之后不久,他的同事很快就接受了这一事实。

“只要有这样的声明,”德克萨斯大学奥斯汀分校理论计算机科学家斯科特·亚伦森在他的博客上写道,“大约99%的时间要么证明是错误的,要么无论如何对于外人评估它来说太复杂了这是其余1%的案例中的一个。我相信证据是正确的。为什么?因为我阅读并理解它。我花了大约半个小时。“

在匹兹堡卡内基梅隆大学(Carnegie Mellon University)研究数论的计算机科学教授赖恩奥唐纳(Ryan O'Donnell)指出,黄的证据可以在一条推文中总结:

郝黄

@Emory :例1:用2 ^ {n-1}的n-cube进行n-cube的签名+/- sqrt(n)

交织=>任何诱导子图> 2 ^ {n-1} vtcs有max eig> = sqrt(n)

例2:在子图中,max eig <= max valency,即使有符号

因此[GL92]灵敏度Conj,s(f)> = sqrt(deg(f))

- Ryan O'Donnell(@BooleanAnalysis),2019年7月1日

黄实际证明了什么?

为简单起见,想象一个三维立方体,每边的长度为1个单位。如果将此立方体放入三维坐标系(意味着它在三个方向上进行测量),则一个角将具有坐标(0,0,0),其旁边的坐标可能为(1,0,0),它上面的一个可能是(0,1,0),依此类推。你可以在没有任何一对邻居的情况下占据一半角(四个角):( 0,0,0),(1,1,0),(1,0,1)和(0,1,1)都是'邻居。您可以通过查看多维数据集来显示此信息,但我们也知道它,因为所有这些都不同于多个坐标。

希伯来大学数学家吉尔卡莱说,这种灵敏度猜想是关于你在占据一个更高维立方体或超立方体的一半以上的角落时找到了多少邻居。Kalai告诉Live Science,您可以将超立方体的坐标写为1s和0s的字符串,其中维度的数量是字符串的长度。例如,对于4D超立方体,有16个不同的点,这意味着16个不同的1s和0s串,长度为4位。

现在在超立方体上选择一半加1个单独的点(对于4D超立方体,这意味着在总共16个中选择9个或8个+ 1个不同的点)。

从这个较小的集合中,找到最邻居的点 - 它可以拥有的最小邻居数量是多少?(邻居只有一个数字。例如,1111和1110是邻居,因为你只需交换一个数字就可以将第一个数字转换成第二个数字。)

Huang证明了这个角必须至少与数字的平方根一样多 - 在这种情况下,4的平方根 - 为2。

对于低维度,您可以通过检查来判断这是真的。例如,检查邻居的多维数据集(或“字符串”)上的16个坐标并不困难。但每次向多维数据集添加维度时,字符串数量都会翻倍。所以问题变得越来越难以快速检查。

长度为30位的字符串集合 - 三维立方体角落的坐标 - 中包含超过10亿个不同的字符串,这意味着立方体有超过10亿个角落。对于长度为200位的字符串,有超过一个novemdecillion。这是一亿亿亿亿亿亿,或1,其次是60零。

这就是为什么数学家喜欢证明:他们表明在每种情况下都是正确的,而不仅仅是简单的。

“如果n等于一百万 - 这意味着我们有长度为100万的字符串 - 那么猜想是如果你取2 ^ 1,000,000-1并加1,那么有一个字符串有1000个邻居 - 平方根百万,“卡莱说。

Kalai说,灵敏度猜想的最后一次重大进展发生在1988年,当研究人员证明一条弦必须至少具有n个邻居的对数时。这是一个低得多的数字; 1,000,000的对数仅为6.因此,Huang的证据发现至少有994个其他邻居在那里。

优雅而“神秘”的证明

“这是非常神秘的,”Kalai谈到黄的证据。“它使用'光谱方法',这是许多数学领域中非常重要的方法。但它以一种新颖的方式使用光谱方法。它仍然是神秘的,但我认为我们可以期待这种使用光谱方法的新方法将逐渐具有更多应用程序。“

实质上,Huang使用行和列中的数字数组(称为矩阵)来概念化超立方体。Aaronson在他的博客中写道,Huang想出了一种完全出人意料的操纵矩阵的方式,这种矩阵具有-1s和1s的不寻常排列,“神奇地使它完全奏效”。

Kalai说,Huang“采用了这种矩阵,并以非常巧妙和神秘的方式对其进行了修改。” “这就像你有一个管弦乐队,他们演奏一些音乐,然后你让一些球员,我不知道,站在他们的头上,音乐变得完全不同 - 就像那样。”

Kalai说,这种不同的音乐证明是猜测猜想的关键。他说,这是神秘的,因为即使数学家理解为什么这种方法在这种情况下起作用,他们也不完全理解这种新的“音乐”,或者在其他情况下它可能是有用的或有趣的。

“30年来,没有任何进展,然后黄浩解决了这个问题,他找到了一个非常简单的证据,证明答案是n的平方根,”Kalai说。“但在这30年中......人们意识到这个问题在计算理论中非常重要。”

Kalai说,Huang的证明令人兴奋,因为它推动了计算机科学领域的发展。但它也值得注意,因为它引入了一种新颖的方法,数学家仍然不确定黄的新方法可能让他们完成什么。

?中国大众文化网-中国纪实文学会主办国内权威文化门户? | 版权所有 | 若非注明 | 均为原创?
㊣ 转载请附上文章链接并注明: 中国大众文化网-中国纪实文学会主办国内权威文化门户 » 这位数学家的“神秘”新方法解决了一个30年前的问题
㊣ 本文永久链接: http://www.dazhong100.net/ttyw/2019-07-31/5032.html
㊣ 投诉/商务合作:⑦①⑧⑨⑦⑧⑤⑨⑧