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

撰文 | 邸利會

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

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

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

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

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

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

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

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

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

“不合群”的敏感度？

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

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

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

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

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

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

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

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

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

N維超方體

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考資料

[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)造

如果你擁有一顆好奇心

如果你渴求知識

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