理論計算機科學中最令人困惑的謎題之一被解開

「自敏感度猜想提出以來，它便是所有組合學和理論計算機科學中最令人沮喪和尷尬的開放性問題之一。」德克薩斯大學奧斯汀分校的理論計算機學家Scott Aaronson在一篇博客中寫道。

Aaronson提到的猜想是一個與計算機電路的基本構件結構有關的猜想，近30年以來，許多人都試圖攻克這一難題，寫出了一篇又一篇長而複雜的論文，但結果都以失敗告終。然而，在一篇於本月初發表在arXiv上的論文中，年輕的數學家黃皓以令人驚嘆的簡潔方法解決了這一猜想。

1.

這個猜想與布爾函數有關，布爾函數是一系列將一串輸入位（0和1）轉換成一個獨個的輸出位的規則。比如它的規則可以是，當輸入字元串中的比特位全部為1時，那麼輸出為1，其他情況則輸出為0；又比如它可以是，當輸入字元串中含有1的個數為偶數時，那麼輸出為0，否則輸出為1。

試想你正在填寫一份銀行貸款的申請表，你需要填寫一系列「是/否」問題，銀行會根據你填寫的答案進行評判，然後決定你是否有資格申請貸款。這個過程就是一個布爾函數，你的每一道「是/否」問題的答案都是一個輸入位，銀行的最終決定是輸出位。

為了度量布爾函數的複雜性，計算機科學家已發展出許多不同的度量方法，每一種都針對的是「輸入字元串中的信息會如何決定輸出位」這一問題的不同方面。例如布爾函數的「敏感度」所描述的就是當一個單個的輸入位被改變時，輸出位因此而改變的可能性。

我們可以用上面的銀行貸款例子來作進一步解釋。假如你的申請沒有通過，於是你想，要是你修改某個問題的答案，是否就可以改變結果？比如在關於收入的問題上，你謊稱自己年薪百萬，而實際上卻並沒有，會不會就可以通過貸款申請？如果修改這個問題的答案真的能反轉結果，那麼計算機科學家會說，布爾函數對這個特定位的值是「敏感的」。

再比如說在這張長長的申請表中有7個關鍵的問題，如果你對這7個問題的任何一個撒謊都能反轉結果，那麼對於你的貸款概況而言，布爾函數的敏感度為7。

敏感度只是測量布爾函數的複雜性的其中一個度量，每種度量都為審視布爾函數的結構提供了一個獨特的視角。然而計算機科學家發現，幾乎所有這些度量都符合一個統一的框架，也就是說其中的任何一個度量的值都可被用來大致衡量其他度量的值，而敏感度似乎是唯一的例外。

1992年，希伯來大學的Noam Nisan和羅格斯大學的Mario Szegedy推測，敏感度也是符合這一框架的。但這麼多年來，一直沒有人能證明這一點，這個猜想成為了布爾函數研究中最突出的待解問題。

現在，埃默里大學的數學家黃皓利用立方體上的點的組合學，用僅僅兩頁紙的篇幅，巧妙地完成了論證。他證明了敏感度猜想！

2.

1992年，Craig Gotsman和Nati Linial就發現，可以將敏感度猜想的證明歸結為解答關於不同維度下的立方體的簡單問題。有一種方法能將含有n個0和1的字元串轉換到n維立方體上的點上，那就是直接用n個字元位作為點的坐標。

例如你有4個2位的字元串——00、01、10和11，就可以分別對應於二維平面上的一個正方形的四個角——(0,0)、(0,1)、(1,0)和(1,1)；再比如你有8個3位的字元串，就可以對應於一個三維立方體的8個角，更高維度也可依次類推。

○ 舉例說明如何將n個輸入位表示成一個n維立方體的坐標，如果電路輸出,為1，則燈泡亮藍光；如果電路輸出為0，則燈泡亮紅光。

而布爾函數可以被視作為用兩種不同顏色（例如紅色表示0，藍色表示1）來對這些角進行著色的規則。如果將一個立方體超過一半的的角著上紅色，那麼是否總有一些紅點會與許多其他的紅點相連？

如果這個集合中所包含的角的個數恰好是那個立方體的一半，那麼就可能沒有一個角是相連的。就比如在三維立方體的8個角中，(0,0,0)、(1,1,0)、(1,0,1)和(0,1,1)這四個點都位於對角線上。但是，只要立方體中超過一半的點被著上了紅色，那麼這些紅點之間就必然有一些是相連的。問題是：這些連接是如何分布的？至少會有一個是高度相連的點嗎？

○ 立方體中有一半以上的點被著上了紅色。

黃皓決定用矩陣來追蹤哪些點是相連的，他想到了用一種已有200年歷史的數學方法——柯西交錯定理（Cauchy interlace theorem），這種方法能將矩陣的特徵值與子矩陣的特徵值聯繫起來。上個月他突然意識到，他只要改變矩陣中的一些數字的符號，就可以完整地將這種方法一直推演到最終結果。通過這種方法，他成功地證明了在一個n維立方體中，任何超過一半的點的集合，都會有某個點至少與其他√n個點相連接——從這個結果可以立即得出敏感度猜想。

3.

人們或許會以為，證明這樣一個已經存在了30年難題，它的論證過程一定非常冗長，而且肯定極度晦澀難懂。有的同行甚至在讀之前就做好了讀完之後發現自己什麼都沒看懂的準備。

然而，黃皓的證明卻異常簡明，許多研究人員一看就全明白了。可以說，這一結果用來證明敏感度猜想綽綽有餘，它所蘊含的能力或許能讓我們對複雜性度量產生新的見解，是我們在未來解答布爾函數分析中的其他問題的一個強有力工具。

而且最重要的是，黃皓的研究結果消除了人們一直以來的一個擔憂，那就是在複雜性度量的世界中，敏感度是否是某種奇怪的異常值。想必有了這個結果後，許多計算機科學家都能睡得更安穩了。

參考鏈接：

https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/

https://www.scottaaronson.com/blog/?p=4229

https://arxiv.org/abs/1907.00847

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！