1992年，布爾函數敏感度猜想被提出。這成為了理論計算機科學近三十年來最重要的開放性問題之一。近日，來自Emory大學計算機與數學科學系的華人教授黃皓，用兩頁紙輕松證明了困擾理論計算機領域數十年的問題。

組成計算機的電路實際上是“與”“或”“非”邏輯電路的組合，多年來，計算機科學家已經開發出許多方法來測量給定布爾函數的複雜性。

科學家們發現，關于布爾函數的度量措施都适用于一個統一的框架，隻有一個複雜性指标似乎不合适：“靈敏度”。1992年，耶路撒冷希伯來大學的Noam Nisan和現在羅格斯大學的Mario Szegedy 推測，“靈敏度”的确适合這一框架，但沒人能證明這一點。“我想說，這可能是布爾函數研究中一個懸而未決的問題。”Servedio說。

現在，Emory大學的數學家黃皓用一個巧妙但簡單的兩頁論證，證明了靈敏度猜想，這個論點關于立方體上的點的組合。

法國國家科學研究中心的Claire Mathieu在接受Skype采訪時曾評價它為：“這隻是一顆美麗的珍珠。”

黃皓是誰？這位華人科學家是怎麼解開30年來一直困擾計算機科學家的問題呢？

一次偶然與猜想的邂逅

2012年末，在受訪美國普林斯頓高等研究院期間，黃先生在與數學家Michael Saks 共進午餐時聽說了敏感性猜想，黃先生是博士後研究員。他立刻被這個猜想的簡潔和優雅所吸引。“從那一刻開始，我開始沉迷于思考它。”他說。

黃将敏感性猜想添加到他感興趣問題的“秘密列表”中，每當他學習新的數學工具時，他都會考慮它是否有幫助。“每次我發表新論文後，我都會回到這個問題，”他說。“當然，我會在一段時間後放棄，并解決一些更現實的問題。”

正如其他研究團體一樣，黃知道，如果數學家可以證明一個關于不同維度立方體上的點集合比較容易陳述的猜想，那麼靈敏度猜想就可以得到解決。從n 個0和1 的字符串到n維立方體上的點有一種自然的映射關系。

在2013年，黃開始認為理解這個問題的最佳途徑可能是通過标準網絡來表示網絡，該矩陣跟蹤哪些點連接，然後檢查一組稱為矩陣特征值的數字。五年來，他一直在重新審視這個想法，沒有成功。

“但至少考慮它可以幫助我很快入睡。”他在Aaronson的博客文章中評論道。

然後在2018年，黃發現了使用一個有200年曆史的稱為Cauchy交錯定理的數學，它将矩陣的特征值與子矩陣的特征值聯系起來，使其成為研究立方體與立方體之間關系的完美工具。黃決定要求國家科學基金會撥款，以進一步探讨這一想法。

上個月，當他坐在馬德裡的一家酒店寫下他的撥款建議時，他突然意識到他可以通過改變他的矩陣中某些數字的符号來推動這種方法的完成。通過這種方式，他能夠證明在n維立方體中超過一半點的任何集合中，将存在某些與其他點的至少 相關的點,靈敏度猜想 也從這個結果中被證明。

“美麗的珍珠”

被法國科學家評為“美麗的珍珠”，這一猜想的證明思路是如何實現的呢？

先從“靈敏度”談起，“靈敏度”是一種度量，捕獲輸入字符串中的信息如何影響輸出位改變，換句話說，布爾函數的“靈敏度”跟蹤翻轉單個輸入位改變輸出位的可能性。

舉個例子，想象一下，你正在填寫銀行貸款申請中的一系列Yes/No問題（問卷調查）。完成後，銀行家将對您的結果進行評分，并告訴您是否有資格獲得貸款。這個過程是一個布爾函數：你的答案是輸入位，而銀行家的決定是輸出位。

如果你的申請被拒絕，你可能想知道你是否可以通過單一問題的選擇而銀行的預判結果 ，比如你口袋裡面真的沒有多少錢時，在收入超過50,000美元那一欄你打了勾，如果這個謊言會導緻預判結果，計算機科學家說布爾函數對該特定位的值“敏感”。比方說，如果有七種不同的謊言，你可以說它們會分别翻轉結果，那麼對于你的貸款資料，布爾函數的靈敏度是7。

為了可視化計算機電路對位翻轉錯誤的敏感程度，我們可以将其n個輸入位表示為n維立方體的坐标，例如，四個兩位字符串00,01,10和11對應于二維平面中正方形的四個角：（0,0）、（0,1）、（1,0）和（1,1）。同樣，八個三位字符串對應于三維立方體的八個角，以此類推到更高的維度。反過來，布爾函數可以被認為是用兩種不同顔色着色這些角的規則，如果最終輸出為1則将立方體的一角标為藍色，反之，則标為紅色。

輸入字符串0,1,1的簡單布爾功能可對應到下圖立方體的一角，如果翻轉第一個字符，我們可以發現對“OR”“AND”（或與）電路的輸出沒有什麼影響，相反，如果你翻轉第三位，對于這個操作來說，輸出是敏感的，标記為紅色。

證明靈敏度猜想可以簡化為回答關于不同維度的立方體的簡單問題：如果你選擇任何超過在立方體的一半角落并将它們染成紅色，是否總有一些紅點與許多其他紅點相連？（這裡，通過“連接”，我們的意思是這兩個點共享立方體的一個外邊緣，而不是跨越對角線。）

根據我們的布爾函數對立方體的每個角進行着色。給定輸入字符串的敏感位數由其相關角和另一種不同顔色的角之間的連接數捕獲，電路的整體靈敏度定義為任何輸入字符串中最大位數的敏感位。

下面例子中，點（0,1,1）和（0,0,1）藍紅色點之間的連接，靈敏度為1；點（0,1,1）和（0,1,0）藍紅色點之間的連接，靈敏度為0；點（1,0,1）和（1,0,0）藍紅色點之間的連接，靈敏度為0；點（1,0,1）和（0,0,1）藍紅色點之間的連接，靈敏度為2。

取最大值，因此該布爾函數的靈敏度為2。

靈敏度猜想有什麼用？

證明靈敏度猜想有什麼用呢？

這種猜想可以應用在許多實例中 ，例如，醫生可能希望在達到診斷之前盡可能少地為患者發送測試，或者機器學習專家可能希望算法在分類之前盡可能少地檢查對象的特征。

其他措施包括尋找将布爾函數編寫為數學表達式的最簡單方法，或者計算銀行家要向老闆展示多少答案以證明他們已做出正确的貸款決策，其中銀行家可以同時詢問幾個問題的“疊加”；甚至還有量子物理學版本的查詢複雜性，弄清楚該測量與其他複雜性測量的關系如何幫助研究人員理解量子算法的局限性。

黃的結果甚至超過了證明靈敏度猜想所必需的結果，這種發現應該會産生關于複雜性度量的新見解。最重要的是，盡管如此，黃的結果仍然令人擔心，在複雜的世界中，敏感性是否可能是一些奇怪的異常值，還需要後續進一步的研究。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!