摘要：提到將來會不會解決更多的理論計算機難題，黃皓說，還是要看機緣——\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