華人學者剛剛解決了布爾函數的敏感度猜想

一位華人學者剛剛解決了敏感度猜想Sensitivity Conjecture，它是理論計算機科學中近三十年來最重要，最令人困惑的開放性問題之一。

鑒於之前評論里有人吐槽說，類似文章全是泛泛而談的一般科普，核心內容一帶而過，就丟出一個鏈接，所以下面詳細說一下敏感度猜想——在漢語網路環境里，相關信息貌似挺少見的。

敏感度猜想，涉及布爾型數據，以及其上的函數關係。

到此為止，就得到了布爾函數敏感性的定義，但是，猜想本身用到的是布爾函數的塊敏感性！

簡單說一下，就是上面步驟③里，x_i的角標不再是i，而是集合A，A本身是集合{1,2，……，n}的某個子集。顯而易見，函數的塊敏感性不再是i從1取到n，而是集合A取遍{1,2，……，n}的全部子集，這裡，相應的s(f)，變為b s(f)。

1994年，數學家Noam Nisan和Mario Szegedy提出了敏感度猜想Sensitivity Conjecture：

存在一個多項式P，對所有的布爾函數f，都成立 bs(f)≤P[s(f)]！

在計算機科學和數理邏輯，乃至代數學裡，布爾函數無疑是是否重要的研究對象。同時，我們知道，布爾函數有許多複雜性測度，並且幾乎所有這些測度——包括決策樹複雜性，證書複雜性，隨機查詢複雜度和其它許許多多——已知都是多項式相關的。

最新證明的提出者、埃默里大學的數學助理教授Hao Huang向我們解釋猜想的價值和意義：「在數學中，布爾函數是最基本的離散主題之一——就像數字，圖形或幾何形狀一樣。但是，其它測度都是多項式相關的，而如果猜想為真，則敏感度也是如此，否則的話，它就是很反常的量。」

「自2012年以來，我一直嘗試攻克這一猜想。」Huang在接受phys.org採訪時說，「但是直到大約一周前，我才捕捉到關鍵思想。我終於找到了那把正確的鑰匙。」

7月15日至19日，將在瑞士蘇黎世召開隨機結構和演算法的國際會議。Huang將在會議上正式發布證明。但是，迫不及待想要了解詳情的朋友可以點擊此處閱讀、下載論文的預印本。

在論文里，Huang先證明n維超立方圖的生成子圖的相關命題，將猜想作為命題的直接推論。其精巧思路和簡單明了的過程，在社交媒體上贏得了計算機科學家和數學家的一片讚譽。

Huang開發出了一種代數方法。「我希望這種方法也有可能應用到對計算機科學的發展至關重要的其他組合和複雜性問題上。」

ps 雖然有人把Hao Huang翻譯成了黃浩，但是在埃默里大學的個人主頁上，並沒有Hao Huang的中文寫法。同時我十分確定，在知乎上看到過這位答主，但是也沒有找到具體的中文名，所以還是按他主頁上的拼音寫法為準。

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