華人學者黃皓兩頁證明解決計算機科學領域難題：布爾函數敏感度猜想

近日，美國艾默里大學計算機與數學科學系教授黃皓（Hao Huang）用一篇短短 6 頁的論文「輕鬆」證明了困擾理論計算機領域數十年的布爾函數敏感度猜想，引發了計算機和數學領域社區的廣泛關注。布爾函數敏感度猜想是理論計算機科學中近三十年來最重要，最令人困惑的開放性問題之一。

論文長度僅有 6 頁，其核心證明內容只有兩頁，不過黃皓為了解決這個問題花費了 7 年時間的思考。

本月初，一篇僅有 6 頁的論文悄悄登上了 arXiv，隨之而來的是學界的轟動。這篇由華人學者黃皓所著的研究解決了困擾計算機科學領域的難題：布爾函數的敏感度猜想（sensitivity conjecture），而這篇論文中實際的證明部分只有兩頁紙。

完成這一壯舉的數學家黃皓來自廣東汕頭，他 2007 年本科畢業於北京大學，博士就讀於加州大學洛杉磯分校（UCLA），師從著名數學家 Benny Sudakov 教授。黃皓於 2012 年獲得博士學位，2012-2014 年受邀訪問普林斯頓高等研究院，現擔任美國艾默里大學數學系助理教授。其主要研究領域包括極值組合、圖論及理論計算機。已經在 JCTB、JCTA、Combinatorica、SIAM J. Discrete Math 等國際著名期刊上發表及接受發表論文 20 余篇。

布爾函數的敏感度猜想主要涉及計算機電路的基礎構造塊結構，迄今已快 30 年。在這二十餘年中，該猜想難倒了許多優秀的計算機科學家，而黃皓提出的證明方法簡單到可以用一篇推文總結：

CMU 計算機科學系教授 Ryan O"Donnell 發推概括了這篇證明。（圖源：https://twitter.com/BooleanAnalysis/status/1145837576487612416）

使用有 200 年歷史的方法解決了 30 年歷史的重量級猜想，有關布爾函數敏感度的證明讓我們感受到了數學之美。人們對於黃皓的論證紛紛表示感嘆：「這是我們看到過最美麗的兩頁證明。」

敏感度猜想涉及布爾函數，布爾函數描述如何基於對布爾輸入的某種邏輯計算確定布爾值輸出，在複雜性理論的問題和數字計算機的晶元設計中扮演基礎角色。

圖源：http://jandan.net/2019/07/13/sensitivity-conjecture.html

這一猜想可以簡單表述為：存在一個多項式 P，對所有的布爾函數 f，都成立 bs(f)≤P[s(f)]！

敏感度猜想

法國國家科學研究中心 Claire Mathieu 用生動的例子介紹了布爾函數及其敏感度。

當你在銀行貸款申請書上填寫一系列 yes/no 問題的時候，填寫完之後，銀行工作人員將對你的填寫結果進行評分，然後告知你是否符合貸款條件。這一過程就是一個布爾函數：你的答案是輸入 bit，銀行工作人員的決策是輸出 bit。

如果你的申請被拒，你可能會覺得如果在回答某一個問題時撒謊是否就可以改變最後的結果，比如在你實際上掙錢數量不超過 5 萬美元時卻表示超過這一數目。如果該謊言能夠改變最終決策結果，那麼這一布爾函數就對特定 bit 的值「敏感」。假如有七個不同的謊言每一個都可以導致最終決策結果反轉，那麼這一布爾函數的敏感度就為 7。

計算機科學家將該布爾函數的敏感度定義為：當查看所有不同貸款資料時所得到的最大敏感度值。某種程度上，它可以計算在模稜兩可的情況下多少問題是真正重要的，這些情況包括只要稍微改變即可情況反轉的申請。

敏感度通常是最容易計算的複雜度度量指標，但是它並非唯一富有啟發性的指標。例如，銀行工作人員不讓你填寫紙質申請，而是進行面談，先問簡單的問題，再根據你的回答進行後續的提問。這時候銀行職員在進行決策前需要提問的最大問題數量就是布爾函數的查詢複雜度（query complexity）。

這一度量指標在很多場景下都會出現，例如醫生在得出診斷結果之前想讓病人儘可能少地進行檢查，或者機器學習專家想讓演算法在進行物體分類之前儘可能少地查看物體的特徵。「在大量場景中，如診斷場景或學習場景，底層規則的 query 複雜度低是非常值得慶幸的。」O"Donnell 表示。

其他度量包括尋找將布爾函數寫為數學表達式的最簡單方法，或者說計算銀行職員應向上司展示多少個答案，才能證明他們做了正確的貸款決定。這裡甚至還有量子物理版本的查詢複雜度，即銀行職員可以在同一時間詢問多個問題的「疊加」。找到這種度量與其他複雜度的關係，可以幫助研究人員了解量子演算法的局限性。

除了敏感度之外，計算機科學家已經證明了所有這些度量都是緊密關聯的。具體而言，它們之間存在多項式關係——例如一個度量可能大致是另一個度量的平方或立方或平方根。

只有敏感度固執地拒絕適應這種簡潔的表示。很多研究人員懷疑敏感度與其他度量之間也存在多項式關係，但人們一直無法證明確實不存在奇特的布爾函數，其敏感度與其他度量具有指數而非多項式關係。這意味著敏感度度量遠小於其他度量。

「這一問題已經困擾了人們三十年。」德克薩斯大學奧斯汀分校計算機科學教授 Scott Aaronson 說道。

尋找解法

黃皓在 2012 年末與普林斯頓高等研究院數學家 Michael Saks 共進午餐的時候聽聞了敏感度猜想，彼時前者還是一名博士後。他立即被這一猜想的簡潔和優雅所吸引了。「從那一刻起，我就開始沉迷於思考這個問題了。」黃皓說道。

黃皓將敏感度猜想加入了他感興趣問題的「秘密清單」中，每當他學習新的數學工具時，他都會思考這些方法是否會對解決敏感度猜想有所幫助。「每次我發表新的論文之後，我總會回過頭來看看這個問題，」黃皓表示。「當然，我也經常在研究一番之後選擇放棄，然後回到更為現實的問題上來。」

數學家黃皓在里斯本。

黃皓明白，正如研究社區普遍認為的一樣，如果數學家可以證明一個有關不同維度立方體上點集合的猜想，那麼敏感度猜想就可以得到解決。從一個 n 個 0 和 1 組成的序列到 n 維立方體上的點有一種自然的方法：只需使用 n 個 bit 作為點的坐標。

例如，有四個兩位字元串 00、01、10 和 11，分別對應二維平面中正方形的四個角：(0,0)、(0,1)、(1,0) 和 (1,1)。同樣，八個三位字元串分別對應三維立方體的八個角……以此類推。布爾函數可以被認為，用兩種不同顏色為這些角進行著色的規則（比如為 0 塗紅色，1 塗上藍色）。

1992 年，現任新澤西理工計算機學院院長 Craig Gotsman 和希伯來大學計算機科學教授 Nati Linial 找出了證明敏感度猜想的思路：通過回答一個有關不同維度立方體的問題將敏感度猜想大大簡化，如果你選擇將超過一半的立方體尖角同時塗為紅色，是否總是有一些紅色點是與其他紅色點相連接？（在這裡，「連接」表示通過立方體的邊相連，而不是通過任何對角線。）

如果你選擇剛好一半的立方體尖角，則很可能紅色點並不會相連接。例如，在三維立方體的八個角中，(0,0,0), (1,1,0), (1,0,1) 和 (0,1,1) 這四個點只是通過對角線相連。但是只要立方體中超過一半的點被塗成紅色，那麼肯定會出現相連接的紅色點。問題在於：這些連接是如何分布的？是否存在一個高度連接的點？

2013 年，黃皓認為理解這一問題的最佳路徑是，使用矩陣表示網路（矩陣可以追蹤相連的點），並檢測矩陣特徵值。之後五年，他一直試驗這個思路，但都沒有成功。

2018 年，黃皓決定使用柯西交錯定理（Cauchy interlace theorem），該定理將矩陣特徵值和子矩陣特徵值關聯起來，因此成為研究立方體及其尖角子集的完美工具。黃皓決定向美國國家科學基金會提交申請，以進一步探索這一思路。

隨後在上個月，當他坐在馬德里的一家旅館中撰寫申請報告時，他突然意識到自己可以通過簡單地改變矩陣中一些數字的符號來直接解決問題。通過這種方式，他可以證明在 n 維立方體中超過一半點的任何集合中，會有一些點和其他點有至少√n 個連接，敏感度猜想問題的證明就從這裡開始。

當黃皓的論文進入 Claire Mathieu 的收件箱時，她的第一反應是「哦——哇」，她說道：「當一個問題已經存在了 30 年，而每個人都已經聽聞過的時候，我們自然認為證明它的方法會看起來冗長而複雜，或者非常高深。」她打開論文並期待看到無法理解的內容。

但是，對於 Mathieu 和其他很多研究者來說，這一證明非常簡單，可以一次消化。「我希望在今年的秋天在每個碩士級別的組合數學課程中講授這一內容——一堂課就夠了。」Mathieu 表示。

黃皓的研究結果甚至超過了證明敏感度猜想所需的必要程度，其推理應該可以形成有關複雜度度量的新見解。「它充實了我們的工具庫，讓我們可以試圖回答布爾函數分析中的其他問題。」哥倫比亞大學計算機科學教授 Rocco Servedio 說道。

當然，更重要的是黃皓的結果讓那些擔憂敏感度可能是複雜度度量世界中的異類的人放心了，Servedio 表示。「我認為在這一證明推出以後，很多人終於能睡得著覺了。」

最後，這裡是黃皓對布爾函數敏感度猜想的兩頁紙證明：

更多詳情參見論文《Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture》（https://arxiv.org/pdf/1907.00847.pdf）。

參考內容：

https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/

來源：遠方的家

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！