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

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

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

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。

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

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

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

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

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

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

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

2.

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

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

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

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

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

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

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

3.

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

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

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