困擾科學(xué)界近30年的難題——自敏感度猜想

“自敏感度猜想提出以來，它便是所有組合學(xué)和理論計算機科學(xué)中最令人沮喪和尷尬的開放性問題之一?！钡驴怂_斯大學(xué)奧斯汀分校的理論計算機學(xué)家Scott Aaronson在一篇博客中寫道。

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

1.

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

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

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

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

再比如說在這張長長的申請表中有7個關(guān)鍵的問題，如果你對這7個問題的任何一個撒謊都能反轉(zhuǎn)結(jié)果，那么對于你的貸款概況而言，布爾函數(shù)的敏感度為7。

敏感度只是測量布爾函數(shù)的復(fù)雜性的其中一個度量，每種度量都為審視布爾函數(shù)的結(jié)構(gòu)提供了一個獨特的視角。然而計算機科學(xué)家發(fā)現(xiàn)，幾乎所有這些度量都符合一個統(tǒng)一的框架，也就是說其中的任何一個度量的值都可被用來大致衡量其他度量的值，而敏感度似乎是唯一的例外。

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

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

2.

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

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

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

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

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

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

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

3.

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

然而，黃皓的證明卻異常簡明，許多研究人員一看就全明白了?？梢哉f，這一結(jié)果用來證明敏感度猜想綽綽有余，它所蘊含的能力或許能讓我們對復(fù)雜性度量產(chǎn)生新的見解，是我們在未來解答布爾函數(shù)分析中的其他問題的一個強有力工具。

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