摘要：提到将来会不会解决更多的理论计算机难题，黄皓说，还是要看机缘——\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“都没有非要做什么，不要做什么，可能看当时的心情，或者刚好对什么类型的问题感兴趣，就很难说，计划好接下去你要干什么。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E诚如张胜誉所猜测的，“整个证明也许是长期思索和尝试下的精妙发现”，的确，从2012年第一次听说这个猜想算起，黄皓的思考持续了6年多，期间他还做着其它的问题。

"\u003Cdiv\u003E\u003Cp class=\"ql-align-justify\"\u003E中文常常把科学家描写的天才而古板，有时还奇葩。今天我们见识生活事业顺利、年轻充满活力的杰出青年科学家。他虽然是数学家，但不古板而乐观开朗。在兼顾现实世界需要他发表文章的同时，六年间坚持悄悄地研究一个横跨组合与计算机理论的一个三十年悬而未决的难题，终于一举攻克之，解决方案简单而优美，为同行交口称赞。这是“赛先生”的“青春之歌”第一篇。欢迎大家投稿或提供信息，让我们更多了解海内外年轻华人科学家。\u003C\u002Fp\u003E\u003Cdiv class=\"pgc-img\"\u003E\u003Cimg src=\"http:\u002F\u002Fp1.pstatp.com\u002Flarge\u002Fpgc-image\u002F0ad93a315de046aa8c8eaa07a1ccdccd\" img_width=\"1004\" img_height=\"754\" alt=\"“珍珠般的美丽”：华人年轻数学家的研究\" inline=\"0\"\u003E\u003Cp class=\"pgc-img-caption\"\u003E\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E\u003Cp class=\"ql-align-justify\"\u003E\u003Cbr\u003E\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E论文作者埃默里（Emory）大学数学系的助理教授黄皓。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E\u003Cstrong\u003E撰文 | 邸利会\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E困扰理论计算机界30年的猜想，被他一页半纸解决了。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E7月1日，一篇论文出现在arXiv上，与通常动辄几十上百页的证明不同，这篇论文连参考文献在内不到6页，实际上整个的证明不到两页。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E文章的作者是埃默里（Emory）大学数学系助理教授黄皓，他2007年曾本科毕业于北京大学。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“证明非常精美，尤为让人欣赏的是它使用工具初等，而且整个证明只有两页（核心其实不到一页）。大家显然都错过了他的这条路。证明中主要用的构造和引理贴合的恰到好处。整个证明也许是长期思索和尝试下的精妙发现，让人赞叹。” 在看到论文后，腾讯杰出科学家张胜誉告诉“赛先生”。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E黄皓所解决的猜想名为“敏感性猜想”（Sensitivity Conjecture），由耶路撒冷希伯来大学的Noam Nisan和现在罗格斯大学的Mario Szegedy在1992年所提出，是具体复杂性理论（concrete complexity）中一个广为人知的猜想。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“我不能想象甚至上帝可以找得到比这更简单对敏感性猜测的证明。” 德克萨斯大学奥斯汀分校的理论计算机科学家Scott Aaronson在发给Quanta杂志的邮件中说。“它是组合论和理论计算机科学中最令人沮丧和难堪的问题之一”，“试图解决它而失败的人们就是离散数学和理论计算机科学的名人堂” Aaronson在博客里写道。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E确实，过去的近30年，很多人都尝试证明或者证否这一猜测，相关的文献也累计了五六十篇，但都没有成功。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“黄皓的证明简单而优雅，以至于人们可能难以找到更好的一个证明！这个问题本身某种程度是孤立于其它课题的，不过，它确实是很知名，之前的办法都没拿下它。很多世界领先的研究者都曾尝试但都失败了。” 爱丁堡大学信息学学院讲师郭珩在邮件中回复“赛先生”。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E没人想到，这个猜想会以这样简洁而优雅的方式得到证明。法国科学研究中心的数学家和计算机科学家Claire Mathieu感叹：“这真漂亮，像是一颗宝贵的珍珠”。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-center\"\u003E\u003Cstrong\u003E“不合群”的敏感度？\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“敏感性猜想”涉及到大概有200年的历史的布尔函数。这个函数在复杂性理论、电子电路设计和芯片设计中都很基本，在密码学里也有重要的角色。函数并不复杂，输入是一段由0和1组成的比特串，输出是0或者1。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E为了研究布尔函数，人们很早定义了十几个关于其复杂性的度量，加上它们的变体和一些后续的新的度量，一共有几十个，敏感度也属于其中的一个。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E你可以这样理解敏感度：对于一个给定的n位比特串，每一位翻转一下（由1变成0或者由0变成1），如果布尔函数的值也发生翻转，那这个位就算一次，最后可以得到有多少个位翻转会改变函数值。这个叫做局部的敏感度。整体的敏感度就是对于所有的n位比特串，取最大的一个局部敏感度。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E对定义在n位比特串上的布尔函数，包括敏感度在内的这几十个度量之间的关系慢慢得到了越来越好的理解。有趣的是，其中有一大类从不同角度定义的度量都“差不多大小”，即每个都不超过另一个的多项式（比如平方或者三次方），属于一个大家庭。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E当然，人们也知道有些度量不属于这个大家庭，但是有一个显著的例外，就是敏感度这个很基本的度量——大家不知道它的位置，虽然一直猜测它是属于这个大家庭的，但没人能给出证明。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“我的工作就是证明了敏感度也和别的一样都是在一个范畴之内。” 黄皓告诉“赛先生”。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E最早接触到这个猜测是在2012年末，那时黄皓在普林斯顿高等研究院做博士后。在和数学家Michael Saks的一次午餐中，他听说了这一猜测，自此念念不忘。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“当时组里大部分人是做理论计算机方向，他们会给我讲他们感兴趣的理论计算机里面比较数学化的问题。” 黄皓回忆说。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E之后的黄皓一直对其情有独钟，每发表一篇文章后，他又会去想这个问题。想不出来又去做其他更现实的问题，之后再回去继续想这一问题——也许有一天柳暗花明呢？\u003C\u002Fp\u003E\u003Cp class=\"ql-align-center\"\u003E\u003Cstrong\u003EN维超方体\u003C\u002Fstrong\u003E\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E同样是在1992年，现任新泽西理工学院的Craig Gotsman和希伯来大学的Nati Linial发现，证明灵敏度猜想的问题和一个图论的问题是等价的。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“敏感性猜想本身的表述是关于理论计算机算法复杂度理论中研究的核心对象布尔函数（Boolean function），但是和理论计算机中的很多问题类似，这个猜想可以规约到了数学的一个分支——组合图论上的问题。” 中国科学技术大学数学系马杰教授说。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E而图论也是黄皓感兴趣的方向。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E图论的研究在理论和实际应用都有重要意义。我们可以把很多实际生活中的事物看成是图论学中的数学研究对象——图（Graph)，比如可以把微信中所有的用户关系抽象成一个图，其中每个用户是图中的一个节点，两两之间的好友关系看成是图中两个节点中的一条边。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003EGotsman和Linial证明，敏感度猜想事实上等价于在N维超方体（hypercube）这一重要图类上证明这样一个数学命题：n维超方体中任意超过一半节点的子结构中都含一个节点，它至少和“很多”其它节点有边相邻；这里“很多”用严格的数学言语讲的话，就是说要至少大于等于关于n的一个多项式函数。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E这样的一个难懂的问题在转成图的问题后，解释起来也变的比较容易。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E你可以想象有一个N维超方体，顶点的坐标是由长度为n的由0和1组成的比特串。如果n＝2，那就有四个顶点，坐标分别为00，01，10，11，如果两个比特串只有一位不同，就连一条边，比如00和01，00和10，10和11，01和11都连着边，但00和11，01和10不连着边。你可以自行想象下三维的情形。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E这种图有一个性质是，如果取一半那么多的顶点，这些顶点可以两两之间没有边，比如二维的情形，取00和11，或者取10和01，它们之间没有边；三维的情形下，你可以取000，110，101和011这四个顶点，也是一半的顶点，它们之间没有边。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“我证明的结果是说，如果你取一半多一个的点的话，必然存在其中的某一个点，至少和√n个你选择的点相邻，从这个是可以推出多项式关系。” 黄皓解释说。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E正如前文所说，这个多项式关系就是敏感度和其它度量相比，一个不太大，另一个也不会太大，另一不太小，另一个也不会太小。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E提到解决问题的关键，黄皓说，他用到的代数的方法，不是那种传统的组合的方法。“有两三个代数的方法，大家都比较熟悉，难度主要是想到怎样把这几样东西组合起来，不是说每样东西有多特别。” 他说。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E就在上个月，当他坐在马德里的一家酒店写项目申请书时，他突然意识到，几样东西可以拼在一起了。很快，他就完成了这个证明，如此简单而明快的证明。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“在黄皓的极为精巧和优美证明中，他首先注意到超方体这个问题可以进一步转换成一个关于矩阵的极值问题，然后人们就可以借助于数学中的代数工具去做更为精细的分析。这是我见过的最为神奇美妙的数学证明之一。从我的观点看，这个证明中最为美妙的地方在于处理矩阵的绝妙技巧以及背后的深邃数学思想；我想这是一个将来一定会写进教科书、在组合数学和理论计算机界具有持续影响力的数学证明。” 马杰说。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E马杰也是黄皓多年的合作者，在他看来，黄皓是一个非常独立的、有自己学术追求的杰出的青年数学家，和他的合作过程中令人非常愉悦，往往能学到很多有意义的数学想法和思考。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“他的这个结果无疑是近些年来整个理论计算机领域的重大创新之一，为华人数学界和计算机学界挣得了巨大的荣誉；非常为他感到骄傲” 马杰说。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E诚如张胜誉所猜测的，“整个证明也许是长期思索和尝试下的精妙发现”，的确，从2012年第一次听说这个猜想算起，黄皓的思考持续了6年多，期间他还做着其它的问题。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E对黄皓来说，和做理论计算机的人交流也是蛮有意思的事情，这两个领域的人有可能再说同一件事，但却在用完全不同的语言来讲。提到将来会不会解决更多的理论计算机难题，黄皓说，还是要看机缘——\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E“都没有非要做什么，不要做什么，可能看当时的心情，或者刚好对什么类型的问题感兴趣，就很难说，计划好接下去你要干什么。” \u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E当法国科学家Claire Mathieu第一次看到论文时，她以为既然三十年人人知道而解决不了这一问题，那么答案恐怕是很长很复杂、或者很深，但一看黄皓的文章发现它简单到大家都能一次就理解。她说：“我预计今年秋天大家就会用它讲课，也许是每一堂硕士水平的组合课都会讲。”\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E今年秋天，你或许就会在课堂上听到这个美妙的证明了。\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E\u003Cbr\u003E\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E参考资料\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E[1] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, arXiv:1907.00847\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E[2] Erica Klarreich, Decades-Old Computer Science Conjecture Solved in Two Pages, https:\u002F\u002Fwww.quantamagazine.org\u002Fmathematician-solves-computer-science-conjecture-in-two-pages-20190725\u002F\u003C\u002Fp\u003E\u003Cp class=\"ql-align-justify\"\u003E赛先生\u003C\u002Fp\u003E\u003C\u002Fdiv\u003E"'.slice(6, -6), groupId: '6718526822293717515