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

困擾科學(xué)界 30 年的難題

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

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

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

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

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

華人科學(xué)家黃皓用7年時間破解

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

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

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

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

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

圖源：Quantamagazine

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

圖源Twitter：CMU計算機(jī)科學(xué)系教授Ryan O'Donnell

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

Quantamagazine最后寫到，“黃皓的研究結(jié)果超過了證明靈敏度猜想所必需的結(jié)果，這種發(fā)現(xiàn)應(yīng)該會產(chǎn)生關(guān)于復(fù)雜性度量的新見解?！备鐐惐葋喆髮W(xué)計算機(jī)科學(xué)教授Rocco Servedio也表示，“它充實(shí)了我們的工具庫，讓我們可以試圖回答布爾函數(shù)分析中的其他問題”，“我認(rèn)為在這一證明推出以后，很多人終于能睡得著覺了?！?/p>