華人學者解開計算機領域 30 年難題：布爾函數敏感度猜想

整理 | 郭芮

出品 | CSDN（ID：CSDNnews）

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

困擾科學界 30 年的難題

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

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

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

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

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

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

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

黃皓（Hao Huang），圖源：Quantamagazine

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

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

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

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

圖源：Quantamagazine

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

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

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

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

參考鏈接：

https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/

https://news.cnblogs.com/n/628833/

https://new.qq.com/omn/20190727/20190727A0B1GX00.html

【END】

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