困擾科學(xué)界 30 年的難題,華人科學(xué)家黃皓用7年時(shí)間破解

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

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

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

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

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

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

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

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

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

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

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

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

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

圖源：Quantamagazine

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

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

而為了解決這個(gè)問(wèn)題，黃皓花費(fèi)了7年時(shí)間來(lái)思考。

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