只用2頁(yè)紙，北大數(shù)學(xué)校友攻破計(jì)算機(jī)30年難題！過(guò)程淺顯直白，看懂僅需線性代數(shù)基礎(chǔ)

邊策 發(fā)自 凹非寺

量子位 報(bào)道 | 公眾號(hào) QbitAI

數(shù)學(xué)世界中有很多猜想，比如哥德巴赫猜想、黎曼猜想，有些問(wèn)題已經(jīng)困擾了全人類幾百年。

如果某一天，某個(gè)人突然跳出來(lái)說(shuō)：“我只用幾頁(yè)紙，就證明了XX猜想?！贝蠹乙欢〞?huì)覺(jué)得這人是個(gè)“民科”。

最近，有位華人數(shù)學(xué)家黃皓宣布，他證明了一個(gè)困擾計(jì)算機(jī)理論界30年的猜想，而且只用了兩頁(yè)紙。乍一看到這則消息，可能很多人的第一反應(yīng)是：不會(huì)又是個(gè)“民科”吧？

然而事情并沒(méi)有這么簡(jiǎn)單。翻閱黃皓的履歷我們會(huì)發(fā)現(xiàn)，他本科畢業(yè)于北大數(shù)學(xué)系，并在2012獲得了UCLA的博士學(xué)位，現(xiàn)在他已經(jīng)是美國(guó)埃默里大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)系的助理教授。

黃皓是真的解決了問(wèn)題。他給出兩頁(yè)證明過(guò)程，只需要本科的知識(shí)就足以理解。數(shù)學(xué)界的同行們?cè)诎葑x過(guò)后，無(wú)不被他大道至簡(jiǎn)的智慧所折服。

我們量子位將以盡量通俗的方式還原證明過(guò)程，與你一起解決這個(gè)跨世紀(jì)難題——布爾函數(shù)敏感度猜想（Boolean function sensitivity conjecture）。

首先，讓我們先從布爾函數(shù)說(shuō)起。

布爾函數(shù)

（以下是布爾函數(shù)的解釋，熟悉編程的同學(xué)可以直接跳到第二部分。）

我們知道，數(shù)字電路都由邏輯門的組合實(shí)現(xiàn)任意功能，最常見(jiàn)的兩種邏輯門是與門和或門。

與門（AND）只有在輸入全是1的時(shí)候，才會(huì)輸出1，否則輸出0。

或門（OR）只要有一個(gè)輸入是1，輸出就是1，只有當(dāng)輸入全是0的時(shí)候，輸出才是0。

同樣在輸入是(1,1)的情況下，與門會(huì)非常敏感，只要其中一個(gè)輸入發(fā)生變化，結(jié)果就會(huì)變成0。而或門只有兩個(gè)輸入全部發(fā)生變化的時(shí)候，結(jié)果才會(huì)變?yōu)?。

與門和或門只有兩個(gè)bit的輸入，是最簡(jiǎn)單的情形。當(dāng)有n個(gè)輸入bit輸入的時(shí)候，情形就變得復(fù)雜起來(lái)。

舉一個(gè)日常的例子，當(dāng)你攢了多年的錢終于湊足首付后，要去銀行申請(qǐng)購(gòu)房貸款。

銀行柜員給了你一張表，里面有很多很多問(wèn)題，你只能回答是或否。最終你填寫的內(nèi)容被一套復(fù)雜的過(guò)程處理，卻得出不能貸款給你的結(jié)論。

這套處理過(guò)程的輸入是布爾變量（是或否），輸出也是布爾變量（是否批準(zhǔn)貸款），因此是一個(gè)布爾函數(shù)。

事后的你再回想起來(lái)，覺(jué)得可以把某些問(wèn)題的回答反過(guò)來(lái)，也許還能通過(guò)申請(qǐng)。最終你發(fā)現(xiàn)需要改掉超過(guò)7個(gè)問(wèn)題，才能改變審批的結(jié)果。

那么我們就說(shuō)，這個(gè)布爾函數(shù)在你最初答案的條件下敏感度是7。

對(duì)于一個(gè)布爾函數(shù)f，在某個(gè)輸入x（x是n個(gè)bit的布爾變量）的情況下，有超過(guò)s個(gè)布爾變量變化時(shí)，結(jié)果才會(huì)反轉(zhuǎn)。我們就說(shuō)布爾函數(shù)f在輸入為x時(shí)的敏感度為s(f,x)。

所有敏感度s(f,x)的最大值s叫做布爾函數(shù)f的敏感度。

1989年，Nisan和Szegedy兩位猜測(cè)，s是關(guān)于n的一個(gè)多項(xiàng)式。這便是布爾函數(shù)敏感度猜想（Boolean function sensitivity conjecture）。

布爾函數(shù)敏感度猜想出現(xiàn)以來(lái)，就一直是計(jì)算機(jī)科學(xué)理論中最令人頭疼的開(kāi)放性問(wèn)題之一。解決了它就解決了邏輯電路、算法上的很多理論問(wèn)題，比如我們熟知的n位二進(jìn)制信號(hào)的奇偶校驗(yàn)。

變成幾何游戲

但是想直接證明布爾函數(shù)敏感度猜想實(shí)在太難了。好在1992年有兩位數(shù)學(xué)家Gotsman和Linial巧妙地把它變成了一個(gè)通俗的幾何游戲。

他們把數(shù)字電路中的n比特轉(zhuǎn)化為n維空間中立方體的頂點(diǎn)。

比如一個(gè)2比特的輸入總共有4種可能性：00、01、10、11。相當(dāng)于正方形的四個(gè)頂點(diǎn)：(0,0)、(0,1)、(1,0)、(1,1)。正方形就是二維空間中立方體。

同樣的，如果是3比特，就對(duì)應(yīng)三維立方體的8個(gè)頂點(diǎn)，以此類推到更高的維度。

在立方體中，相鄰的兩個(gè)頂點(diǎn)只有一個(gè)坐標(biāo)值有差異，分別為0和1，其他坐標(biāo)值則完全相同。

因此，從立方體中的一個(gè)頂點(diǎn)移到它的相鄰頂點(diǎn)，就相當(dāng)于把布爾函數(shù)輸入中的某個(gè)比特進(jìn)行翻轉(zhuǎn)。（妙?。。?/p>

既然布爾函數(shù)的輸入可以用頂點(diǎn)坐標(biāo)來(lái)表示，那么輸出呢？我們可以用兩種顏色來(lái)定義。

比如用紅色表示0，藍(lán)色表示1。如果某個(gè)頂點(diǎn)是紅色，意味著頂點(diǎn)三個(gè)坐標(biāo)值組成的3比特輸入布爾函數(shù)后會(huì)得到0。

舉個(gè)例子：

在上圖的那個(gè)布爾函數(shù)中，若輸入是(0,1,1)，輸出將會(huì)是1。

倘若我們把第一位翻轉(zhuǎn)，好在布爾函數(shù)對(duì)這個(gè)變化并不敏感，輸出仍然是1，在圖中相當(dāng)于把頂點(diǎn)移到了它的右邊，顏色還是藍(lán)色。

然而第三位翻轉(zhuǎn)后，布爾函數(shù)對(duì)這個(gè)變化是敏感的，輸出變?yōu)?，相當(dāng)于把頂點(diǎn)移到了它的下邊，顏色從藍(lán)色變成紅色。

如果在某種情況下，輸入結(jié)果的任何一位發(fā)生翻轉(zhuǎn)，輸出結(jié)果都會(huì)從1變成0，那也就意味著這個(gè)藍(lán)點(diǎn)周圍都是紅點(diǎn)，這個(gè)點(diǎn)的敏感度就是0，沒(méi)有藍(lán)點(diǎn)與它直接相連。

一個(gè)點(diǎn)周圍與它同色的點(diǎn)的數(shù)量，等于布爾函數(shù)在這個(gè)頂點(diǎn)的敏感度。布爾函數(shù)的敏感度就是所有頂點(diǎn)敏感度中的最大值。

于是布爾函數(shù)敏感度猜想可以簡(jiǎn)化為N維立方體上的簡(jiǎn)單問(wèn)題：

如果將n維立方體的超過(guò)一半的頂點(diǎn)染成紅色，其余染成藍(lán)色，是否總有一些紅點(diǎn)有同色的鄰居？如果有，周圍紅點(diǎn)的數(shù)量最多是多少？

Gotsman和Linial兩位的原話是這樣的：

設(shè)S是n維布爾超立方體{0,1}?ⁿ任意子集，其大小為2^n-1+1。那么在S中必然存在一個(gè)點(diǎn)，在S中至少有n^c個(gè)鄰居。（2^n-1+1恰好比n維立方體的總頂點(diǎn)數(shù)一半多1個(gè)。）

其中c是一個(gè)介于0和1之間的常數(shù)，后面我們可以看到c=1/2。

如果被染成紅色的頂點(diǎn)恰好等于總頂點(diǎn)數(shù)的一半。它們可能互不相鄰。在三維立方體中就能找到一個(gè)例子：四個(gè)點(diǎn)（0,0,0），（1,1,0），（1,0,1）和（0,1,1）恰好都斜跨對(duì)角線。（下圖中的紅點(diǎn)）

但是，只要哪怕多增加一個(gè)點(diǎn)涂成紅色，紅點(diǎn)之間就必須出現(xiàn)連接。

靈感突發(fā)

即使布爾函數(shù)敏感度猜想已經(jīng)在27年前已經(jīng)被簡(jiǎn)化，但是這個(gè)問(wèn)題還是被繼續(xù)擱置了20多年。

直到7年前，當(dāng)時(shí)博士剛剛畢業(yè)的黃皓，和新澤西州立大學(xué)的數(shù)學(xué)教授Michael Saks一起吃飯，聽(tīng)對(duì)方聊到這個(gè)猜想。

黃皓默默地把這個(gè)問(wèn)題加到了自己的“任務(wù)清單”里。

借助柯西

為了解決這個(gè)問(wèn)題，黃皓想到使用一個(gè)200年前的數(shù)學(xué)定理：柯西交錯(cuò)定理（Cauchy interlace theorem）。

這個(gè)定理將矩陣與它的子矩陣的特征值聯(lián)系起來(lái)，使其成為研究高低維立方體之間關(guān)系的完美工具。二維立方體(正方形)是三維立方體的一個(gè)面，因此是后者的一個(gè)子集。

柯西交錯(cuò)定理的表述如下：

A是一個(gè)n×n階矩陣，B是A的m×m階主子矩陣(m<n)。矩陣A的特征值為λ_1?≥ λ₂?≥ ? ? ? ≥λ_n，矩陣B的特征值為μ₁?≥ μ₂?≥ ? ? ? ≥μm，那么：

已經(jīng)接近答案了，還差點(diǎn)什么呢？可能是錢吧。

黃皓決定申請(qǐng)美國(guó)國(guó)家科學(xué)基金會(huì)撥款，進(jìn)一步研究探討這一問(wèn)題。

就在上個(gè)月，黃皓坐在馬德里的一家酒店里，寫他的科研基金申請(qǐng)書時(shí)，突然靈感迸發(fā)：可以改變矩陣中某些數(shù)字的符號(hào)，推動(dòng)證明過(guò)程，直至得出結(jié)果。

他構(gòu)造了一組2ⁿ×2ⁿ階矩陣，定義為：

可以很容易用數(shù)學(xué)歸納法證明：

根據(jù)矩陣特征值的定義，A_n的特征值只能是√n 和-√n 。

而A_n的對(duì)角元素全部是0，因此矩陣的跡Tr(A_n)=0。我們知道矩陣的跡等于所有特征值之和，所以√n 和-√n 的數(shù)量必須相等，都是2^n-1個(gè)。

相鄰矩陣

如果H是一個(gè)有m個(gè)頂點(diǎn)的圖（由點(diǎn)和它們之間連線組成的圖形），A是一個(gè)對(duì)稱矩陣，并且A是圖H的相鄰矩陣。

所謂相鄰矩陣，是指A的第u行第v列元素表示H的第u個(gè)點(diǎn)和第v個(gè)點(diǎn)是否相鄰，如果不相鄰，這個(gè)元素就等于0；如果相鄰，這個(gè)元素就是-1或者1；此外對(duì)角元素必須等于0。

容易驗(yàn)證，前面我們構(gòu)造的矩陣A_n就是n維立方體Qⁿ的相鄰矩陣。

假設(shè)圖H是n維立方體的一部分（準(zhǔn)確地說(shuō)，叫做立方體Qⁿ的誘導(dǎo)子圖），那么H的相鄰矩陣是A_n的一個(gè)主子矩陣。

假設(shè)λ₁是矩陣A的最大本征值，v是λ₁對(duì)應(yīng)的本征向量，v₁是本征向量v里絕對(duì)值最大的一個(gè)分量。

上面推導(dǎo)過(guò)程中第一個(gè)不等號(hào)成立的原因是和的絕對(duì)值小于絕對(duì)值的和。

第二個(gè)不等號(hào)也很簡(jiǎn)單：?(H)是圖H的敏感度，而左邊是某個(gè)點(diǎn)的敏感度，圖的敏感度是其所有點(diǎn)敏感度的最大值。

所以?(H)≥|λ₁|，即圖H的敏感度?(H)大于矩陣A的最大本征值的絕對(duì)值。

A是A_n的子矩陣。倘若H包含2^n-1+1個(gè)頂點(diǎn)，帶入到柯西交錯(cuò)定理中：

前面已經(jīng)證明?(H)≥|λ₁|，所以?(H)≥√n，而?(H)就是n個(gè)bit布爾函數(shù)的敏感度。

證明完畢！

通過(guò)這種簡(jiǎn)單的方式，黃皓證明了：在n維立方體中超過(guò)一半點(diǎn)的任何子集中，總會(huì)有一些點(diǎn)連接到至少√n 個(gè)其他同色的點(diǎn)，從這個(gè)結(jié)果中可以立即得出敏感度猜想。

尾巴

“我希望黃皓今年秋天能夠在碩士的組合數(shù)學(xué)課程講授（證明過(guò)程），只要一節(jié)課就夠了?！?/p>

法國(guó)國(guó)家科研中心的Clarie Mathieu看到了黃皓的證明時(shí)，不禁感嘆證明過(guò)程的簡(jiǎn)單。

黃皓的結(jié)果甚至超過(guò)了證明靈敏度猜想所必需的結(jié)果，應(yīng)該還會(huì)產(chǎn)生關(guān)于復(fù)雜性度量的新見(jiàn)解。比如用于n位二進(jìn)制字符串的奇偶校驗(yàn)算法。

“它增加了我們的工具包，可以幫助回答布爾函數(shù)分析中的其他問(wèn)題，”哥倫比亞大學(xué)計(jì)算機(jī)科學(xué)教授Servedio說(shuō)，“我認(rèn)為很多人在聽(tīng)到這個(gè)消息之后會(huì)在那個(gè)晚上睡得更輕松?！?/p>

不知道是什么讓黃皓突然產(chǎn)生了靈感，但是有位網(wǎng)友說(shuō)出了一種可能性：寫科研基金申請(qǐng)或許真的能幫助科研吧（笑）。

關(guān)于黃皓

黃皓2007年從北京大學(xué)數(shù)學(xué)系畢業(yè)，赴加州大學(xué)洛杉磯分校深造，于2012年獲得數(shù)學(xué)系博士學(xué)位，并獲得當(dāng)年的學(xué)位論文獎(jiǎng)學(xué)金。

他畢業(yè)后在普林斯頓大學(xué)高等研究院、明尼蘇達(dá)大學(xué)數(shù)學(xué)研究所從事博士后研究工作，之后進(jìn)入埃默里大學(xué)數(shù)學(xué)系，擔(dān)任助理教授，先后在Journal of Combinatorial Theory等學(xué)術(shù)期刊上發(fā)表過(guò)21篇學(xué)術(shù)論文。

黃皓的主要研究方向是極值與概率組合、結(jié)構(gòu)圖論、理論計(jì)算機(jī)科學(xué)。

傳送門

論文鏈接：

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

https://arxiv.org/abs/1907.00847