建站
咨詢
售后
建站咨詢
新聞中心
近日，美國(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é)中近三十年來最重要，最令人困惑的開放性問題之一。
創(chuàng)新互聯(lián)網(wǎng)站建設(shè)提供從項(xiàng)目策劃、軟件開發(fā)，軟件安全維護(hù)、網(wǎng)站優(yōu)化(SEO)、網(wǎng)站分析、效果評(píng)估等整套的建站服務(wù)，主營(yíng)業(yè)務(wù)為成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)，重慶APP開發(fā)以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。創(chuàng)新互聯(lián)深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！
論文長(zhǎng)度僅有 6 頁(yè)，其核心證明內(nèi)容只有兩頁(yè)，不過黃皓為了解決這個(gè)問題花費(fèi)了 7 年時(shí)間的思考。
本月初，一篇僅有 6 頁(yè)的論文悄悄登上了 arXiv，隨之而來的是學(xué)界的轟動(dòng)。這篇由華人學(xué)者黃皓所著的研究解決了困擾計(jì)算機(jī)科學(xué)領(lǐng)域的難題：布爾函數(shù)的敏感度猜想（sensitivity conjecture），而這篇論文中實(shí)際的證明部分只有兩頁(yè)紙。
完成這一壯舉的數(shù)學(xué)家黃皓來自廣東汕頭，他 2007 年本科畢業(yè)于北京大學(xué)，博士就讀于加州大學(xué)洛杉磯分校（UCLA），師從著名數(shù)學(xué)家 Benny Sudakov 教授。黃皓于 2012 年獲得博士學(xué)位，2012-2014 年受邀訪問普林斯頓高等研究院，現(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ì)于黃皓的論證紛紛表示感嘆：「這是我們看到過最美麗的兩頁(yè)證明。」
敏感度猜想涉及布爾函數(shù)，布爾函數(shù)描述如何基于對(duì)布爾輸入的某種邏輯計(jì)算確定布爾值輸出，在復(fù)雜性理論的問題和數(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)書上填寫一系列 yes/no 問題的時(shí)候，填寫完之后，銀行工作人員將對(duì)你的填寫結(jié)果進(jìn)行評(píng)分，然后告知你是否符合貸款條件。這一過程就是一個(gè)布爾函數(shù)：你的答案是輸入 bit，銀行工作人員的決策是輸出 bit。
如果你的申請(qǐng)被拒，你可能會(huì)覺得如果在回答某一個(gè)問題時(shí)撒謊是否就可以改變最后的結(jié)果，比如在你實(shí)際上掙錢數(shù)量不超過 5 萬美元時(shí)卻表示超過這一數(shù)目。如果該謊言能夠改變最終決策結(jié)果，那么這一布爾函數(shù)就對(duì)特定 bit 的值「敏感」。假如有七個(gè)不同的謊言每一個(gè)都可以導(dǎo)致最終決策結(jié)果反轉(zhuǎn)，那么這一布爾函數(shù)的敏感度就為 7。
計(jì)算機(jī)科學(xué)家將該布爾函數(shù)的敏感度定義為：當(dāng)查看所有不同貸款資料時(shí)所得到的最大敏感度值。某種程度上，它可以計(jì)算在模棱兩可的情況下多少問題是真正重要的，這些情況包括只要稍微改變即可情況反轉(zhuǎn)的申請(qǐng)。
敏感度通常是最容易計(jì)算的復(fù)雜度度量指標(biāo)，但是它并非唯一富有啟發(fā)性的指標(biāo)。例如，銀行工作人員不讓你填寫紙質(zhì)申請(qǐng)，而是進(jìn)行面談，先問簡(jiǎn)單的問題，再根據(jù)你的回答進(jìn)行后續(xù)的提問。這時(shí)候銀行職員在進(jì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ù)寫為數(shù)學(xué)表達(dá)式的最簡(jiǎn)單方法，或者說計(jì)算銀行職員應(yīng)向上司展示多少個(gè)答案，才能證明他們做了正確的貸款決定。這里甚至還有量子物理版本的查詢復(fù)雜度，即銀行職員可以在同一時(shí)間詢問多個(gè)問題的「疊加」。找到這種度量與其他復(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)系，但人們一直無法證明確實(shí)不存在奇特的布爾函數(shù)，其敏感度與其他度量具有指數(shù)而非多項(xiàng)式關(guān)系。這意味著敏感度度量遠(yuǎn)小于其他度量。
「這一問題已經(jīng)困擾了人們?nèi)??！沟驴怂_斯大學(xué)奧斯汀分校計(jì)算機(jī)科學(xué)教授 Scott Aaronson 說道。
尋找解法
黃皓在 2012 年末與普林斯頓高等研究院數(shù)學(xué)家 Michael Saks 共進(jìn)午餐的時(shí)候聽聞了敏感度猜想，彼時(shí)前者還是一名博士后。他立即被這一猜想的簡(jiǎn)潔和優(yōu)雅所吸引了?！笍哪且豢唐?，我就開始沉迷于思考這個(gè)問題了?！裹S皓說道。
黃皓將敏感度猜想加入了他感興趣問題的「秘密清單」中，每當(dāng)他學(xué)習(xí)新的數(shù)學(xué)工具時(shí)，他都會(huì)思考這些方法是否會(huì)對(duì)解決敏感度猜想有所幫助?！该看挝野l(fā)表新的論文之后，我總會(huì)回過頭來看看這個(gè)問題，」黃皓表示。「當(dāng)然，我也經(jīng)常在研究一番之后選擇放棄，然后回到更為現(xiàn)實(shí)的問題上來?！?/p>
數(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 和希伯來大學(xué)計(jì)算機(jī)科學(xué)教授 Nati Linial 找出了證明敏感度猜想的思路：通過回答一個(gè)有關(guān)不同維度立方體的問題將敏感度猜想大大簡(jiǎn)化，如果你選擇將超過一半的立方體尖角同時(shí)涂為紅色，是否總是有一些紅色點(diǎn)是與其他紅色點(diǎn)相連接？（在這里，「連接」表示通過立方體的邊相連，而不是通過任何對(duì)角線。）
如果你選擇剛好一半的立方體尖角，則很可能紅色點(diǎn)并不會(huì)相連接。例如，在三維立方體的八個(gè)角中，(0,0,0), (1,1,0), (1,0,1) 和 (0,1,1) 這四個(gè)點(diǎn)只是通過對(duì)角線相連。但是只要立方體中超過一半的點(diǎn)被涂成紅色，那么肯定會(huì)出現(xiàn)相連接的紅色點(diǎn)。問題在于：這些連接是如何分布的？是否存在一個(gè)高度連接的點(diǎn)？
2013 年，黃皓認(rèn)為理解這一問題的最佳路徑是，使用矩陣表示網(wǎng)絡(luò)（矩陣可以追蹤相連的點(diǎn)），并檢測(cè)矩陣特征值。之后五年，他一直試驗(yàn)這個(gè)思路，但都沒有成功。
2018 年，黃皓決定使用柯西交錯(cuò)定理（Cauchy interlace theorem），該定理將矩陣特征值和子矩陣特征值關(guān)聯(lián)起來，因此成為研究立方體及其尖角子集的完美工具。黃皓決定向美國(guó)國(guó)家科學(xué)基金會(huì)提交申請(qǐng)，以進(jìn)一步探索這一思路。
隨后在上個(gè)月，當(dāng)他坐在馬德里的一家旅館中撰寫申請(qǐng)報(bào)告時(shí)，他突然意識(shí)到自己可以通過簡(jiǎn)單地改變矩陣中一些數(shù)字的符號(hào)來直接解決問題。通過這種方式，他可以證明在 n 維立方體中超過一半點(diǎn)的任何集合中，會(huì)有一些點(diǎn)和其他點(diǎn)有至少√n 個(gè)連接，敏感度猜想問題的證明就從這里開始。
當(dāng)黃皓的論文進(jìn)入 Claire Mathieu 的收件箱時(shí)，她的第一反應(yīng)是「哦——哇」，她說道：「當(dāng)一個(gè)問題已經(jīng)存在了 30 年，而每個(gè)人都已經(jīng)聽聞過的時(shí)候，我們自然認(rèn)為證明它的方法會(huì)看起來冗長(zhǎng)而復(fù)雜，或者非常高深?！顾蜷_論文并期待看到無法理解的內(nèi)容。
但是，對(duì)于 Mathieu 和其他很多研究者來說，這一證明非常簡(jiǎn)單，可以一次消化。「我希望在今年的秋天在每個(gè)碩士級(jí)別的組合數(shù)學(xué)課程中講授這一內(nèi)容——一堂課就夠了。」Mathieu 表示。
黃皓的研究結(jié)果甚至超過了證明敏感度猜想所需的必要程度，其推理應(yīng)該可以形成有關(guān)復(fù)雜度度量的新見解。「它充實(shí)了我們的工具庫(kù)，讓我們可以試圖回答布爾函數(shù)分析中的其他問題?！垢鐐惐葋喆髮W(xué)計(jì)算機(jī)科學(xué)教授 Rocco Servedio 說道。
當(dāng)然，更重要的是黃皓的結(jié)果讓那些擔(dān)憂敏感度可能是復(fù)雜度度量世界中的異類的人放心了，Servedio 表示?！肝艺J(rèn)為在這一證明推出以后，很多人終于能睡得著覺了?！?/p>
最后，這里是黃皓對(duì)布爾函數(shù)敏感度猜想的兩頁(yè)紙證明：
更多詳情參見論文《Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture》（https://arxiv.org/pdf/1907.00847.pdf）。
本文標(biāo)題：華人學(xué)者解開計(jì)算機(jī)領(lǐng)域30年難題：布爾函數(shù)敏感度猜想
鏈接地址：http://www.5511xx.com/article/dpohppc.html
