只用2頁紙，北大數(shù)學校友攻破計算機30年難題！過程淺顯直白，看懂僅需線性代數(shù)基礎

邊策 發(fā)自 凹非寺

量子位 報道 | 公眾號 QbitAI

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

如果某一天，某個人突然跳出來說：“我只用幾頁紙，就證明了XX猜想?！贝蠹乙欢〞X得這人是個“民科”。

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

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

黃皓是真的解決了問題。他給出兩頁證明過程，只需要本科的知識就足以理解。數(shù)學界的同行們在拜讀過后，無不被他大道至簡的智慧所折服。

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

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

布爾函數(shù)

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

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

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

或門（OR）只要有一個輸入是1，輸出就是1，只有當輸入全是0的時候，輸出才是0。

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

與門和或門只有兩個bit的輸入，是最簡單的情形。當有n個輸入bit輸入的時候，情形就變得復雜起來。

舉一個日常的例子，當你攢了多年的錢終于湊足首付后，要去銀行申請購房貸款。

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

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

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

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

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

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

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

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

變成幾何游戲

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

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

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

同樣的，如果是3比特，就對應三維立方體的8個頂點，以此類推到更高的維度。

在立方體中，相鄰的兩個頂點只有一個坐標值有差異，分別為0和1，其他坐標值則完全相同。

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

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

比如用紅色表示0，藍色表示1。如果某個頂點是紅色，意味著頂點三個坐標值組成的3比特輸入布爾函數(shù)后會得到0。

舉個例子：

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

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

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

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

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

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

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

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

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

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

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

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

靈感突發(fā)

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

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

黃皓默默地把這個問題加到了自己的“任務清單”里。

借助柯西

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

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

柯西交錯定理的表述如下：

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

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

黃皓決定申請美國國家科學基金會撥款，進一步研究探討這一問題。

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

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

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

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

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

相鄰矩陣

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

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

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

假設圖H是n維立方體的一部分（準確地說，叫做立方體Qⁿ的誘導子圖），那么H的相鄰矩陣是A_n的一個主子矩陣。

假設λ₁是矩陣A的最大本征值，v是λ₁對應的本征向量，v₁是本征向量v里絕對值最大的一個分量。

上面推導過程中第一個不等號成立的原因是和的絕對值小于絕對值的和。

第二個不等號也很簡單：?(H)是圖H的敏感度，而左邊是某個點的敏感度，圖的敏感度是其所有點敏感度的最大值。

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

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

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

證明完畢！

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

尾巴

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

法國國家科研中心的Clarie Mathieu看到了黃皓的證明時，不禁感嘆證明過程的簡單。

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

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

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

關(guān)于黃皓

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

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

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

傳送門

論文鏈接：

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

https://arxiv.org/abs/1907.00847