論文作者埃默里（Emory）大學(xué)數(shù)學(xué)系的助理教授黃皓。

撰文 | 邸利會(huì)

困擾理論計(jì)算機(jī)界30年的猜想，被他一頁半紙解決了。

7月1日，一篇論文出現(xiàn)在arXiv上，與通常動(dòng)輒幾十上百頁的證明不同，這篇論文連參考文獻(xiàn)在內(nèi)不到6頁，實(shí)際上整個(gè)的證明不到兩頁。

文章的作者是埃默里（Emory）大學(xué)數(shù)學(xué)系助理教授黃皓，他2007年曾本科畢業(yè)于北京大學(xué)。

“證明非常精美，尤為讓人欣賞的是它使用工具初等，而且整個(gè)證明只有兩頁（核心其實(shí)不到一頁）。大家顯然都錯(cuò)過了他的這條路。證明中主要用的構(gòu)造和引理貼合的恰到好處。整個(gè)證明也許是長期思索和嘗試下的精妙發(fā)現(xiàn)，讓人贊嘆?！?在看到論文后，騰訊杰出科學(xué)家張勝譽(yù)告訴“賽先生”。

黃皓所解決的猜想名為“敏感性猜想”（Sensitivity Conjecture），由耶路撒冷希伯來大學(xué)的Noam Nisan和現(xiàn)在羅格斯大學(xué)的Mario Szegedy在1992年所提出，是具體復(fù)雜性理論（concrete complexity）中一個(gè)廣為人知的猜想。

“我不能想象甚至上帝可以找得到比這更簡單對敏感性猜測的證明。” 德克薩斯大學(xué)奧斯汀分校的理論計(jì)算機(jī)科學(xué)家Scott Aaronson在發(fā)給Quanta雜志的郵件中說。“它是組合論和理論計(jì)算機(jī)科學(xué)中最令人沮喪和難堪的問題之一”，“試圖解決它而失敗的人們就是離散數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)的名人堂” Aaronson在博客里寫道。

確實(shí)，過去的近30年，很多人都嘗試證明或者證否這一猜測，相關(guān)的文獻(xiàn)也累計(jì)了五六十篇，但都沒有成功。

“黃皓的證明簡單而優(yōu)雅，以至于人們可能難以找到更好的一個(gè)證明！這個(gè)問題本身某種程度是孤立于其它課題的，不過，它確實(shí)是很知名，之前的辦法都沒拿下它。很多世界領(lǐng)先的研究者都曾嘗試但都失敗了?！?愛丁堡大學(xué)信息學(xué)學(xué)院講師郭珩在郵件中回復(fù)“賽先生”。

沒人想到，這個(gè)猜想會(huì)以這樣簡潔而優(yōu)雅的方式得到證明。法國科學(xué)研究中心的數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家Claire Mathieu感嘆：“這真漂亮，像是一顆寶貴的珍珠”。

“不合群”的敏感度？

“敏感性猜想”涉及到大概有200年的歷史的布爾函數(shù)。這個(gè)函數(shù)在復(fù)雜性理論、電子電路設(shè)計(jì)和芯片設(shè)計(jì)中都很基本，在密碼學(xué)里也有重要的角色。函數(shù)并不復(fù)雜，輸入是一段由0和1組成的比特串，輸出是0或者1。

為了研究布爾函數(shù)，人們很早定義了十幾個(gè)關(guān)于其復(fù)雜性的度量，加上它們的變體和一些后續(xù)的新的度量，一共有幾十個(gè)，敏感度也屬于其中的一個(gè)。

你可以這樣理解敏感度：對于一個(gè)給定的n位比特串，每一位翻轉(zhuǎn)一下（由1變成0或者由0變成1），如果布爾函數(shù)的值也發(fā)生翻轉(zhuǎn)，那這個(gè)位就算一次，最后可以得到有多少個(gè)位翻轉(zhuǎn)會(huì)改變函數(shù)值。這個(gè)叫做局部的敏感度。整體的敏感度就是對于所有的n位比特串，取最大的一個(gè)局部敏感度。

對定義在n位比特串上的布爾函數(shù)，包括敏感度在內(nèi)的這幾十個(gè)度量之間的關(guān)系慢慢得到了越來越好的理解。有趣的是，其中有一大類從不同角度定義的度量都“差不多大小”，即每個(gè)都不超過另一個(gè)的多項(xiàng)式（比如平方或者三次方），屬于一個(gè)大家庭。

當(dāng)然，人們也知道有些度量不屬于這個(gè)大家庭，但是有一個(gè)顯著的例外，就是敏感度這個(gè)很基本的度量——大家不知道它的位置，雖然一直猜測它是屬于這個(gè)大家庭的，但沒人能給出證明。

“我的工作就是證明了敏感度也和別的一樣都是在一個(gè)范疇之內(nèi)。” 黃皓告訴“賽先生”。

最早接觸到這個(gè)猜測是在2012年末，那時(shí)黃皓在普林斯頓高等研究院做博士后。在和數(shù)學(xué)家Michael Saks的一次午餐中，他聽說了這一猜測，自此念念不忘。

“當(dāng)時(shí)組里大部分人是做理論計(jì)算機(jī)方向，他們會(huì)給我講他們感興趣的理論計(jì)算機(jī)里面比較數(shù)學(xué)化的問題?！?黃皓回憶說。

之后的黃皓一直對其情有獨(dú)鐘，每發(fā)表一篇文章后，他又會(huì)去想這個(gè)問題。想不出來又去做其他更現(xiàn)實(shí)的問題，之后再回去繼續(xù)想這一問題——也許有一天柳暗花明呢？

N維超方體

同樣是在1992年，現(xiàn)任新澤西理工學(xué)院的Craig Gotsman和希伯來大學(xué)的Nati Linial發(fā)現(xiàn)，證明靈敏度猜想的問題和一個(gè)圖論的問題是等價(jià)的。

“敏感性猜想本身的表述是關(guān)于理論計(jì)算機(jī)算法復(fù)雜度理論中研究的核心對象布爾函數(shù)（Boolean function），但是和理論計(jì)算機(jī)中的很多問題類似，這個(gè)猜想可以規(guī)約到了數(shù)學(xué)的一個(gè)分支——組合圖論上的問題。” 中國科學(xué)技術(shù)大學(xué)數(shù)學(xué)系馬杰教授說。

而圖論也是黃皓感興趣的方向。

圖論的研究在理論和實(shí)際應(yīng)用都有重要意義。我們可以把很多實(shí)際生活中的事物看成是圖論學(xué)中的數(shù)學(xué)研究對象——圖（Graph)，比如可以把微信中所有的用戶關(guān)系抽象成一個(gè)圖，其中每個(gè)用戶是圖中的一個(gè)節(jié)點(diǎn)，兩兩之間的好友關(guān)系看成是圖中兩個(gè)節(jié)點(diǎn)中的一條邊。

Gotsman和Linial證明，敏感度猜想事實(shí)上等價(jià)于在N維超方體（hypercube）這一重要圖類上證明這樣一個(gè)數(shù)學(xué)命題：n維超方體中任意超過一半節(jié)點(diǎn)的子結(jié)構(gòu)中都含一個(gè)節(jié)點(diǎn)，它至少和“很多”其它節(jié)點(diǎn)有邊相鄰；這里“很多”用嚴(yán)格的數(shù)學(xué)言語講的話，就是說要至少大于等于關(guān)于n的一個(gè)多項(xiàng)式函數(shù)。

這樣的一個(gè)難懂的問題在轉(zhuǎn)成圖的問題后，解釋起來也變的比較容易。

你可以想象有一個(gè)N維超方體，頂點(diǎn)的坐標(biāo)是由長度為n的由0和1組成的比特串。如果n＝2，那就有四個(gè)頂點(diǎn)，坐標(biāo)分別為00，01，10，11，如果兩個(gè)比特串只有一位不同，就連一條邊，比如00和01，00和10，10和11，01和11都連著邊，但00和11，01和10不連著邊。你可以自行想象下三維的情形。

這種圖有一個(gè)性質(zhì)是，如果取一半那么多的頂點(diǎn)，這些頂點(diǎn)可以兩兩之間沒有邊，比如二維的情形，取00和11，或者取10和01，它們之間沒有邊；三維的情形下，你可以取000，110，101和011這四個(gè)頂點(diǎn)，也是一半的頂點(diǎn)，它們之間沒有邊。

“我證明的結(jié)果是說，如果你取一半多一個(gè)的點(diǎn)的話，必然存在其中的某一個(gè)點(diǎn)，至少和√n個(gè)你選擇的點(diǎn)相鄰，從這個(gè)是可以推出多項(xiàng)式關(guān)系?！?黃皓解釋說。

正如前文所說，這個(gè)多項(xiàng)式關(guān)系就是敏感度和其它度量相比，一個(gè)不太大，另一個(gè)也不會(huì)太大，另一不太小，另一個(gè)也不會(huì)太小。

提到解決問題的關(guān)鍵，黃皓說，他用到的代數(shù)的方法，不是那種傳統(tǒng)的組合的方法?！坝袃扇齻€(gè)代數(shù)的方法，大家都比較熟悉，難度主要是想到怎樣把這幾樣?xùn)|西組合起來，不是說每樣?xùn)|西有多特別?！?他說。

就在上個(gè)月，當(dāng)他坐在馬德里的一家酒店寫項(xiàng)目申請書時(shí)，他突然意識(shí)到，幾樣?xùn)|西可以拼在一起了。很快，他就完成了這個(gè)證明，如此簡單而明快的證明。

“在黃皓的極為精巧和優(yōu)美證明中，他首先注意到超方體這個(gè)問題可以進(jìn)一步轉(zhuǎn)換成一個(gè)關(guān)于矩陣的極值問題，然后人們就可以借助于數(shù)學(xué)中的代數(shù)工具去做更為精細(xì)的分析。這是我見過的最為神奇美妙的數(shù)學(xué)證明之一。從我的觀點(diǎn)看，這個(gè)證明中最為美妙的地方在于處理矩陣的絕妙技巧以及背后的深邃數(shù)學(xué)思想；我想這是一個(gè)將來一定會(huì)寫進(jìn)教科書、在組合數(shù)學(xué)和理論計(jì)算機(jī)界具有持續(xù)影響力的數(shù)學(xué)證明?！?馬杰說。

馬杰也是黃皓多年的合作者，在他看來，黃皓是一個(gè)非常獨(dú)立的、有自己學(xué)術(shù)追求的杰出的青年數(shù)學(xué)家，和他的合作過程中令人非常愉悅，往往能學(xué)到很多有意義的數(shù)學(xué)想法和思考。

“他的這個(gè)結(jié)果無疑是近些年來整個(gè)理論計(jì)算機(jī)領(lǐng)域的重大創(chuàng)新之一，為華人數(shù)學(xué)界和計(jì)算機(jī)學(xué)界掙得了巨大的榮譽(yù)；非常為他感到驕傲” 馬杰說。

誠如張勝譽(yù)所猜測的，“整個(gè)證明也許是長期思索和嘗試下的精妙發(fā)現(xiàn)”，的確，從2012年第一次聽說這個(gè)猜想算起，黃皓的思考持續(xù)了6年多，期間他還做著其它的問題。

對黃皓來說，和做理論計(jì)算機(jī)的人交流也是蠻有意思的事情，這兩個(gè)領(lǐng)域的人有可能再說同一件事，但卻在用完全不同的語言來講。提到將來會(huì)不會(huì)解決更多的理論計(jì)算機(jī)難題，黃皓說，還是要看機(jī)緣——

“都沒有非要做什么，不要做什么，可能看當(dāng)時(shí)的心情，或者剛好對什么類型的問題感興趣，就很難說，計(jì)劃好接下去你要干什么?！?nbsp;

當(dāng)法國科學(xué)家Claire Mathieu第一次看到論文時(shí)，她以為既然三十年人人知道而解決不了這一問題，那么答案恐怕是很長很復(fù)雜、或者很深，但一看黃皓的文章發(fā)現(xiàn)它簡單到大家都能一次就理解。她說：“我預(yù)計(jì)今年秋天大家就會(huì)用它講課，也許是每一堂碩士水平的組合課都會(huì)講?！?/p>

今年秋天，你或許就會(huì)在課堂上聽到這個(gè)美妙的證明了。

參考資料

[1] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, arXiv:1907.00847

[2] Erica Klarreich, Decades-Old Computer Science Conjecture Solved in Two Pages, https://www./mathematician-solves-computer-science-conjecture-in-two-pages-20190725/

啟蒙·探索·創(chuàng)造

如果你擁有一顆好奇心

如果你渴求知識(shí)

如果你相信世界是可以理解的