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

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

1.

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

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

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

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

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

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

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

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

2.

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

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

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

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

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

○立方體中有一半以上的點(diǎn)被著上了紅色。

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

3.

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

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

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