【為什麼我們要挑選這篇文章】布林函數（Boolean function）是一種邏輯函數，用來分析與推算「真」與「假」的邏輯關係，也就是說，它只處理 0 與 1 兩種狀態的數值，是電腦科學裡的關鍵函數。敏感度討論的是，如果我們改變輸入的某個值，會對輸出的值產生多大程度的影響。
布林函數的敏感度是理論電腦最重要的問題之一，困擾了科學家 30 年，近期終於被一個教授破解了，而且整個算式只占了兩頁紙。他是怎麼解開這個難題的？（責任編輯：郭家宏）
「《科技報橘》徵才中！跟我們一起定位台灣產業創新力 >> 詳細職缺訊息
快將你的履歷自傳寄至 [email protected]」
1992 年，布林函數（Boolean function）敏感度猜想被提出。這成為了理論電腦科學近三十年來最重要的開放性問題之一。2019 年 7 月，來自 Emory 大學電腦與數學科學系的華人教授黃皓，用兩頁紙輕鬆證明了困擾理論電腦領域數十年的問題。
組成電腦的電路實際上是「與」「或」「非」邏輯電路的組合，多年來，電腦科學家已經開發出許多方法來測量給定布林函數的複雜性。
科學家們發現，關於布林函數的度量措施都適用於一個統一的框架，只有一個複雜性指標似乎不合適：「敏感度」。1992 年，耶路撒冷希伯來大學的 Noam Nisan 和現在羅格斯大學的 Mario Szegedy 推測，「敏感度」的確適合這一框架，但沒人能證明這一點。「我想說，這可能是布林函數研究中一個懸而未決的問題」Servedio 說。
現在，Emory 大學的數學家黃皓用一個巧妙但簡單的兩頁論證，證明了敏感度猜想，這個論點關於立方體上的點的組合。
法國國家科學研究中心的 Claire Mathieu 在接受 Skype 採訪時曾評價它為：「這只是一顆美麗的珍珠。」
黃皓是誰？這位華人科學家是怎麼解開 30 年來一直困擾電腦科學家的問題呢？
黃皓：保送北大數學系，並獲得加州大學博士學位
黃皓出生於汕頭，這座海濱城市同時也是另一位著名數學家丘成桐的出生地。
14 歲的時候，黃皓就離開家鄉奔赴廣州華南師範大學附屬中學就讀。憑藉優異的成績，2003 年黃皓被保送至北京大學攻讀數學專業。在北大就讀時，黃皓就在北京大學舉辦的首屆「江澤涵」杯數學建模與電腦應用競賽中獲得三等獎，並出現在北大數學百年學生名錄上。
2007 年北大本科畢業後，黃皓在美國加州大學洛杉磯分校讀博，師從國際著名數學家 Benny Sudakov 教授，並於 2012 年獲得博士學位。
曾在 2012 到 2014 年受邀訪問美國普林斯頓高等研究院，現擔任美國艾默裡大學數學系助理教授。主要研究領域包括極值組合、圖論及電腦理論。
黃皓使用 Cauchy 交錯定理，解決布林函數的敏感度問題
2012 年末，在受訪美國普林斯頓高等研究院期間，黃先生在與數學家 Michael Saks 共進午餐時聽說了敏感性猜想。黃先生是博士後研究員，他立刻被這個猜想的簡潔和優雅所吸引。「從那一刻開始，我開始沉迷於思考它」他說。
黃將敏感性猜想添加到他感興趣問題的「秘密列表」中，每當他學習新的數學工具時，他都會考慮它是否有幫助。「每次我發表新論文後，我都會回到這個問題，」他說。「當然，我會在一段時間後放棄，並解決一些更現實的問題。」
正如其他研究團體一樣，黃知道，如果數學家可以證明一個關於不同維度立方體上的點集合比較容易陳述的猜想，那麼敏感度猜想就可以得到解決。從 n 個 0 和 1 的字元串到 n 維立方體上的點有一種自然的映射關係。
在 2013 年，黃開始認為理解這個問題的最佳途徑可能是透過標準網路來表示網路，該矩陣跟蹤哪些點連接，然後檢查一組稱為矩陣特徵值（Eigenvalue）的數字。5 年來，他一直在重新審視這個想法，沒有成功。
「但至少考慮它可以幫助我很快入睡。」他在 Aaronson 的博客（部落格）文章中評論道。
然後在 2018 年，黃使用一個有 200 年歷史，稱為 Cauchy 交錯定理的數學，它將矩陣的特徵值與子矩陣的特徵值聯繫起來，使其成為研究立方體與立方體之間關係的完美工具。黃決定要求國家科學基金會撥款，以進一步探討這一想法。
上個月，當他坐在馬德里的一家酒店寫下他的撥款建議時，他突然意識到他可以透過改變他的矩陣中某些數字的符號來推動這種方法的完成。透過這種方式，他能夠證明在 n 維立方體中超過一半點的任何集合中，將存在某些與其他點的至少 n 開根號的相關的點，敏感度猜想也從這個結果中被證明。
什麼是敏感度？它指的是系統輸入值的改變對輸出值的影響程度
被法國科學家評為「美麗的珍珠」，這一猜想的證明思路是如何實現的呢？
先從「敏感度」談起，敏感度是一種度量，捕獲輸入字元串中的訊息如何影響輸出位改變，換句話說，布林函數的「敏感度」跟蹤翻轉單個輸入位改變輸出位的可能性。
舉個例子，想像一下，你正在填寫銀行貸款申請中的一系列 Yes/No 問題（問卷調查）。完成後，銀行家將對您的結果進行評分，並告訴您是否有資格獲得貸款。這個過程是一個布林函數：你的答案是輸入位，而銀行家的決定是輸出位。
如果你的申請被拒絶，你可能想知道你是否可以透過單一問題的選擇而銀行的預判結果 ，比如你口袋裡面真的沒有多少錢時，在收入超過 50,000 美元那一欄你打了勾，如果這個謊言會影響判斷結果，電腦科學家說布林函數對該特定位的值「敏感」。比如說，如果有 7 種不同的謊言，你可以說它們會分別翻轉結果，那麼對於你的貸款資料，布林函數的敏感度是 7。
為了視覺化電腦電路對位翻轉錯誤的敏感程度，我們可以將其 n 個輸入位表示為 n 維立方體的坐標，例如，四個兩位字元串 00、01、10 和 11 對應於二維平面中正方形的四個角：（0,0）、（0,1）、（1,0）和（1,1）。同樣，8 個三位字元串對應於三維立方體的 8 個角，以此類推到更高的維度。反過來，布林函數可以被認為是用兩種不同顏色著色這些角的規則，如果最終輸出為 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。
敏感度猜想的應用：簡化數學算式與演算過程
證明敏感度猜想有什麼用呢？
這種猜想可以應用在許多實例中 ，例如，醫生可能希望在達到診斷之前，儘可能少為患者發送測試，或者機器學習專家可能希望演算法在分類之前，儘可能少檢查對象的特徵。
其他措施包括尋找將布林函數編寫為數學表達式的最簡單方法，或者計算銀行家要向老闆展示多少答案以證明他們已做出正確的貸款決策，其中銀行家可以同時詢問幾個問題的「疊加」；甚至還有量子物理學版本的查詢複雜性，弄清楚該測量與其他複雜性測量的關係如何幫助研究人員理解量子演算法的侷限性。
黃的結果甚至超過了證明敏感度猜想所必需的結果，這種發現應該會產生關於複雜性度量的新見解。最重要的是，儘管如此，黃的結果仍然令人擔心，在複雜的世界中，敏感性是否可能是一些奇怪的異常值，還需要後續進一步的研究。
原文報導傳送門
（本文經合作夥伴 大數據文摘 授權轉載，並同意 TechOrange 編寫導讀與修訂標題，原文標題為〈困扰计算机圈近三十年的布尔函数敏感度猜想，被华人数学家2页纸解决了！〉。首圖來源：大數據文摘）
更多關於演算法的知識
【打開演算法的黑箱子】用「臉部辨識」演算法指認罪犯，會出現什麼大問題？
1992 年的一種演算法，是微信用來審查敏感圖片的關鍵技術！
揭秘「AlphaStar」演算法！看 AI 如何在《星海爭霸 2》血洗職業玩家
