[[271995]]

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

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

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

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

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

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

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

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

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

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

敏感度猜想

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

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

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

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

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

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

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

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

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

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

尋找解法

黃皓在 2012 年末與普林斯頓高等研究院數(shù)學(xué)家 Michael Saks 共進(jìn)午餐的時(shí)候聽(tīng)聞了敏感度猜想，彼時(shí)前者還是一名博士后。他立即被這一猜想的簡(jiǎn)潔和優(yōu)雅所吸引了。「從那一刻起，我就開(kāi)始沉迷于思考這個(gè)問(wèn)題了?！裹S皓說(shuō)道。

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

[[271996]]

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

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

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

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

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

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

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

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

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

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

黃皓的研究結(jié)果甚至超過(guò)了證明敏感度猜想所需的必要程度，其推理應(yīng)該可以形成有關(guān)復(fù)雜度度量的新見(jiàn)解?！杆鋵?shí)了我們的工具庫(kù)，讓我們可以試圖回答布爾函數(shù)分析中的其他問(wèn)題?！垢鐐惐葋喆髮W(xué)計(jì)算機(jī)科學(xué)教授 Rocco Servedio 說(shuō)道。

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

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

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