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

困擾科學界 30 年的難題

多年來，計算機科學家已經開發(fā)出許多方法來測量給定布爾函數的復雜性。研究發(fā)現(xiàn)，關于布爾函數復雜性的度量措施都適用于一個統(tǒng)一的框架，但有一個復雜性指標似乎并不適用——“靈敏度”。靈敏度（sensitivity conjecture）是一種衡量布爾函數復雜度的方法，它被定義為導致布爾函數翻轉的最大比特數，通過捕獲輸入字符串中的信息來影響輸出位的改變。換句話說，布爾函數的“靈敏度”跟蹤翻轉單個輸入位改變輸出位的可能性。

1992年，耶路撒冷希伯來大學的Noam Nisan和現(xiàn)在羅格斯大學的Mario Szegedy 推測表示，“靈敏度”同樣是適合統(tǒng)一框架的，但沒有人能證明這一點，這也成為了布爾函數研究中一個懸而未決的問題。

靈敏度猜想的證明具有很大的實踐意義，主要涉及計算機電路的基礎構造塊結構，包括：醫(yī)生可以在達到診斷之前盡可能少地為患者發(fā)送測試；機器學習專家可以通過算法在分類之前盡可能少地檢查對象的特征；銀行家可以向老板展示盡量少的答案以證明他們已做出正確的貸款決策；甚至還涉及量子物理學版本的查詢復雜性，弄清楚該測量與其他復雜性測量的關系可以幫助研究人員理解量子算法的局限性......

外媒Quantamagazine就此問題舉例說：如果你向銀行申請貸款，那么就需要填一系列答案為是或否的問題，銀行再根據你的答案進行評分做出決定——這個過程就是一個布爾函數，你的答案就是輸入比特，銀行的決定就是輸出比特。如果你改變某個問題的答案會導致結果翻轉，這個比特/答案就被定義為敏感了，如果有7個問題任意一個翻轉會導致結果翻轉，那么其敏感度就是7。

在這二十多年中，該猜想難倒了許多優(yōu)秀的計算機科學家。而現(xiàn)在，Emory大學的數學家黃皓用一個巧妙但簡單的兩頁論證，證明了靈敏度猜想。

華人科學家黃皓用7年時間破解

本月初，一篇僅有6頁的論文悄悄登上了arXiv，引起了學術界的轟動。一位名叫黃皓（Hao Huang）的華人科學家解開了30年來一直困擾計算機科學家的問題，論文長度僅有6頁，其核心證明內容只有2頁。

黃皓出生于汕頭，十四歲時離開家鄉(xiāng)奔赴廣州華南師范大學附屬中學就讀，憑借優(yōu)異的成績于2003年被保送至北京大學攻讀數學專業(yè)。2007年北大本科畢業(yè)后，黃皓在美國加州大學洛杉磯分校（UCLA）讀博，師從國際著名數學家Benny Sudakov教授，并于2012年獲得博士學位。2012-2014年受邀訪問普林斯頓高等研究院，現(xiàn)擔任美國艾默里大學數學系助理教授。其主要研究領域包括極值組合、圖論及理論計算機，已經在JCTB、JCTA、Combinatorica、SIAM J. Discrete Math等國際著名期刊上發(fā)表及接受發(fā)表論文20余篇。

2012年末，在受訪美國普林斯頓高等研究院期間，黃皓在與數學家Michael Saks共進午餐時聽說了敏感性猜想，他立刻被這個猜想的簡潔和優(yōu)雅所吸引。“每次我發(fā)表新論文后，我都會回到這個問題，”他說。“當然，我會在一段時間后放棄，并解決一些更現(xiàn)實的問題。”

在2013年，黃皓開始認為理解這個問題的最佳途徑可能是通過標準網絡來表示網絡，該矩陣跟蹤哪些點連接，然后檢查一組稱為矩陣特征值的數字。五年來，他一直在重新審視這個想法，但一直沒有成功。2018年，黃皓發(fā)現(xiàn)了使用一個有200年歷史的稱為Cauchy交錯定理的數學，它將矩陣的特征值與子矩陣的特征值聯(lián)系起來，使其成為研究立方體與立方體之間關系的完美工具。

上個月，他突然意識到他可以通過改變他的矩陣中某些數字的符號來推動這種方法的完成。通過這種方式，他能夠證明在n維立方體中超過一半點的任何集合中，將存在某些與其他點相關的點，靈敏度猜想也從這個結果中被證明。

圖源：Quantamagazine

這個存在了30年的難題，最終證明是如此簡潔甚至可以用一條推文概況。

圖源Twitter：CMU計算機科學系教授Ryan O'Donnell

而為了解決這個問題，黃皓花費了7年時間來思考。

Quantamagazine最后寫到，“黃皓的研究結果超過了證明靈敏度猜想所必需的結果，這種發(fā)現(xiàn)應該會產生關于復雜性度量的新見解。”哥倫比亞大學計算機科學教授Rocco Servedio也表示，“它充實了我們的工具庫，讓我們可以試圖回答布爾函數分析中的其他問題”，“我認為在這一證明推出以后，很多人終于能睡得著覺了。”