[[271995]]

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

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

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

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

布爾函數(shù)的敏感度猜想主要涉及計算機(jī)電路的基礎(chǔ)構(gòu)造塊結(jié)構(gòu)，迄今已快 30 年。在這二十余年中，該猜想難倒了許多優(yōu)秀的計算機(jī)科學(xué)家，而黃皓提出的證明方法簡單到可以用一篇推文總結(jié)：

CMU 計算機(jī)科學(xué)系教授 Ryan O'Donnell 發(fā)推概括了這篇證明。（圖源：https://twitter.com/BooleanAnalysis/status/1145837576487612416）

使用有 200 年歷史的方法解決了 30 年歷史的重量級猜想，有關(guān)布爾函數(shù)敏感度的證明讓我們感受到了數(shù)學(xué)之美。人們對于黃皓的論證紛紛表示感嘆：「這是我們看到過最美麗的兩頁證明?！?/span>

敏感度猜想涉及布爾函數(shù)，布爾函數(shù)描述如何基于對布爾輸入的某種邏輯計算確定布爾值輸出，在復(fù)雜性理論的問題和數(shù)字計算機(jī)的芯片設(shè)計中扮演基礎(chǔ)角色。

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

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

敏感度猜想

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

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

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

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

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

這一度量指標(biāo)在很多場景下都會出現(xiàn)，例如醫(yī)生在得出診斷結(jié)果之前想讓病人盡可能少地進(jìn)行檢查，或者機(jī)器學(xué)習(xí)專家想讓算法在進(jìn)行物體分類之前盡可能少地查看物體的特征。「在大量場景中，如診斷場景或?qū)W習(xí)場景，底層規(guī)則的 query 復(fù)雜度低是非常值得慶幸的。」O'Donnell 表示。

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

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

只有敏感度固執(zhí)地拒絕適應(yīng)這種簡潔的表示。很多研究人員懷疑敏感度與其他度量之間也存在多項式關(guān)系，但人們一直無法證明確實不存在奇特的布爾函數(shù)，其敏感度與其他度量具有指數(shù)而非多項式關(guān)系。這意味著敏感度度量遠(yuǎn)小于其他度量。

「這一問題已經(jīng)困擾了人們?nèi)辍！沟驴怂_斯大學(xué)奧斯汀分校計算機(jī)科學(xué)教授 Scott Aaronson 說道。

尋找解法

黃皓在 2012 年末與普林斯頓高等研究院數(shù)學(xué)家 Michael Saks 共進(jìn)午餐的時候聽聞了敏感度猜想，彼時前者還是一名博士后。他立即被這一猜想的簡潔和優(yōu)雅所吸引了?！笍哪且豢唐穑揖烷_始沉迷于思考這個問題了。」黃皓說道。

黃皓將敏感度猜想加入了他感興趣問題的「秘密清單」中，每當(dāng)他學(xué)習(xí)新的數(shù)學(xué)工具時，他都會思考這些方法是否會對解決敏感度猜想有所幫助?！该看挝野l(fā)表新的論文之后，我總會回過頭來看看這個問題，」黃皓表示。「當(dāng)然，我也經(jīng)常在研究一番之后選擇放棄，然后回到更為現(xiàn)實的問題上來?！?/span>

[[271996]]

數(shù)學(xué)家黃皓在里斯本。

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

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

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

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

2013 年，黃皓認(rèn)為理解這一問題的最佳路徑是，使用矩陣表示網(wǎng)絡(luò)（矩陣可以追蹤相連的點），并檢測矩陣特征值。之后五年，他一直試驗這個思路，但都沒有成功。

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

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

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

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

黃皓的研究結(jié)果甚至超過了證明敏感度猜想所需的必要程度，其推理應(yīng)該可以形成有關(guān)復(fù)雜度度量的新見解?！杆鋵嵙宋覀兊墓ぞ邘欤屛覀兛梢栽噲D回答布爾函數(shù)分析中的其他問題?！垢鐐惐葋喆髮W(xué)計算機(jī)科學(xué)教授 Rocco Servedio 說道。

當(dāng)然，更重要的是黃皓的結(jié)果讓那些擔(dān)憂敏感度可能是復(fù)雜度度量世界中的異類的人放心了，Servedio 表示。「我認(rèn)為在這一證明推出以后，很多人終于能睡得著覺了。」

最后，這里是黃皓對布爾函數(shù)敏感度猜想的兩頁紙證明：

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