[情報] 華人數學家用2頁解決布林敏感度猜想

[bulls0722 (asdf)]

1992年，耶路撒冷希伯來大學的Noam Nisan和羅格斯大學的Mario Szegedy提出布林函數
敏感度猜想。這成為了計算機科學近三十年來最重要的開放性問題之一。這個月，Emor
y大學的華人教授黃皓用兩頁紙證明了此問題。

證明在連結p3,p4

http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf

電腦科學家發明了各種衡量布林函數複雜度的方法。布林函數的敏感度就是將某輸入位
元反轉後使得輸出被反轉的機會。而“查詢複雜度”則是你需要確定多少個輸入位元才
能定下輸出位元。

每一種測度都以獨特的視角審視布林函數的結構。電腦科學家們發現幾乎所有測度都在
統一框架內互相相關，知道其中一個測量值讓你可以估計其它測量值。而這其中唯一的
格格不入者正是敏感度。

想像你在向銀行申請貸款，需要填一系列答案為是或否的問題。填完後銀行人員會告訴
你是否批准貸款。這個過程就是一個布林函數，你的答案是輸入位元，而銀行人員的決
定是輸出位元。

如果你的申請被拒，你也許會想在某個問題上撒謊來改變結果，例如年薪是否為5萬以上
，如果改變這個回答就能徹底反轉最後的決定，電腦科學家稱該布林函數對於這個特定
位元“敏感”。如果有7個問題的答案任一改一下都能改變結果，此布林函數的敏感度為
7。

電腦科學家把布林函數的敏感度定義為在所有可能的申請中最大的那個敏感度值。換句
話說，這個測度計算在最極端的情況下，有多少道問題是真正至關重要的？而最多需要
幾個問題可以做出決定就是布林函數的查詢複雜度。

除了敏感度以外，電腦科學家已經證明了所有測度值之間都成多項式關係。例如，一個
測度值可能大約是另一個測度值的平方，或立方，或平方根。只有敏感度尚未融入到這
個優美的框架之中。

黃皓在2012年從數學家Michael Saks聽到了這個猜想。他立刻被這個猜想的簡潔優美吸
引了。“自那一刻起，我不斷固執地思索著這個問題。”

黃皓知道如果數學家能證明某個關於不同維度下方形頂點集合的簡潔猜想，那麼敏感度
猜想就等於被證明了。n個輸入位元0或1和n維方形頂點有一種自然的映射關係，它可以
被視為該頂點的座標。

舉例而言，2位元串共有4種情況00, 01, 10和11，對應於二維平面上正方形的頂點(0,0),
 (0,1), (1,0)和(1,1)。同樣，8個3位元串對應于三維立方的8個頂點，更高維下也以此
類推。布林函數等於把所有頂點塗上兩種不同顏色的方法（例如輸出為1塗藍色，0塗紅
色）。

2013年，黃皓認為證明的最佳思路為將網路轉化為一個代表兩點是否相連的矩陣，並探
索這個矩陣的特徵值。在接下來的5年裡，他不斷重溫這個思路，但一直沒有突破。“至
少思考這個問題經常讓我很快入眠。”

2018年，黃皓突然意識到可以借用柯西交錯定理。這個定理將矩陣的特徵值和其子矩陣
的特徵值掛勾，這意味著用該定理來研究方形和其頂點子集再恰當不過了。

黃皓決定向國家科學基金申請經費，當他坐在馬德里的酒店裡寫申請書時，突發意識到
只要把矩陣裡某些數的符號逆轉就能把問題完全解決。這麼一來，他能證明n維方形中任
一超過一半頂點的集合中，必有一點和至少n個其它同在該集合中的點相連。敏感度猜想
終於被證明。

當同行評審Mathieu收到黃皓的論文時，她已經做好完全看不懂的準備。但是證明非常簡
潔，Mathieu和其他同行一讀完就理解了。她說：“我覺得今年秋天所有組合數學碩士課
程都可以教這個定理了，而且一節課就可以教完。”

黃皓簡介: 出生於汕頭，2003年憑藉優異的成績被保送至北京大學攻讀數學。黃皓在北
京大學舉辦數學建模與計算機應用競賽中獲得三等獎，並出現在北大數學百年學生名錄
上。2007年畢業後，黃皓在美國加州大學洛杉磯分校讀博，師從著名數學家Benny Suda
kov教授，並於2012年獲得學位。現擔任Emory大學數學系助理教授。主要研究領域包括
極值組合、圖論及計算機理論。
推 tipsofwarren: 恭喜!
推 ruokcnn: @@
推 h5904098: 有趣推
※ 編輯: bulls0722 (42.72.69.32 臺灣), 07/31/2019 15:02:00
推 email81227: 感謝分享!!
推 yyawlin: Mmmm, 我看懂了，下次我在課堂上可以用20分鐘證給學生看
→ yyawlin: 了...