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

2021-01-12 CSDN

整理 | 郭芮

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】

相關焦點

  • 七年思考,兩頁證明,華人學者解開計算機領域30年難題:布爾函數敏感...
    機器之心報導參與：李澤南、路近日，美國艾默裡大學計算機與數學科學系教授黃皓（Hao Huang）用一篇短短 6 頁的論文「輕鬆」證明了困擾理論計算機領域數十年的布爾函數敏感度猜想，引發了計算機和數學領域社區的廣泛關注。布爾函數敏感度猜想是理論計算機科學中近三十年來最重要，最令人困惑的開放性問題之一。
  • 困擾計算機圈近三十年的布爾函數敏感度猜想,華人數學家解決了
    布爾函數敏感度猜想被提出。這成為了理論計算機科學近三十年來最重要的開放性問題之一。近日，來自Emory大學計算機與數學科學系的華人教授黃皓，用兩頁紙輕鬆證明了困擾理論計算機領域數十年的問題。 組成計算機的電路實際上是「與」「或」「非」邏輯電路的組合，多年來，計算機科學家已經開發出許多方法來測量給定布爾函數的複雜性。
  • 只用2頁紙,北大數學校友攻破計算機30年難題!過程淺顯直白,看懂僅...
    最近，有位華人數學家黃皓宣布，他證明了一個困擾計算機理論界30年的猜想，而且只用了兩頁紙。乍一看到這則消息，可能很多人的第一反應是：不會又是個「民科」吧？然而事情並沒有這麼簡單。我們量子位將以儘量通俗的方式還原證明過程，與你一起解決這個跨世紀難題——布爾函數敏感度猜想（Boolean function sensitivity conjecture）。首先，讓我們先從布爾函數說起。布爾函數（以下是布爾函數的解釋，熟悉編程的同學可以直接跳到第二部分。）
  • 159年!這個被譽為「千禧年七大難題」的猜想解開了?
    黎曼猜想——一個來自159年前的數學「腦洞」。 提到「黎曼猜想」，不得不提的還有Zeta函數。
  • 160年難題,黎曼猜想被他證明了?
    此前，這位菲爾茲獎和阿貝爾獎的雙料得主宣布，已證明世紀難題黎曼猜想。就在演講前，網傳一份證明黎曼假設（猜想）的的5頁預印本被人貼出。DeepTech深科技刊文稱，從這次會議來看，阿蒂亞實際上並沒有完全給出黎曼猜想的證明，他的工作似乎集中在試圖推導出精細結構常數上，而證明黎曼猜想只是個意外的驚喜。無論結果如何，阿蒂亞的演講引發了一次空前的科普盛世，推動分支學科進行更深入的交叉。
  • 難題不會永遠是難題，76歲時他解開電磁學界「哥德巴赫猜想」​|紀念林為幹院士
    林為幹是中國電磁場與微波技術學科的主要奠基人、新中國50年重大貢獻科學家之一，他在76歲時解開電磁學界的「哥德巴赫猜想」。1892年，英國科學家麥克斯韋出版了《電磁學》（第三版），書中他提出「點電荷在介質球中能夠形成多大的鏡像，位於何處」的問題。這個難題被譽為電磁學界「哥德巴赫猜想」。解開這個百年未解的難題是很多電磁學家的夢想。
  • 世紀難題「黎曼猜想」被證明了?它究竟說了個啥?
    新華社記者羅歡歡攝9月24日英國著名數學家麥可·阿提亞在第6屆海德堡國際數學與計算機科學獲獎者論壇上提出了證明黎曼猜想的「簡單思路」並稱沿著該思路可以證明黎曼猜想這是德國數學家希爾伯特在1900年提出的23個問題中唯一懸而未決的重大問題，也是2000年美國克萊數學研究所公布的世界七大數學難題之一。159年前，德國數學家黎曼在題為《論小於給定數值的素數個數》的論文中提出了「黎曼猜想」。這篇論文雖然只有8頁，卻給後世留下了數學史上最著名的未決問題。
  • 困擾數學家90年的猜想,被計算機搜索30分鐘解決了
    就連困擾人類90年的數學猜想也擋不住。來自斯坦福、CMU等高校的4名數學家，將一個數學難題轉化成了對10億個結果進行「暴力搜索」。△ 論文作者之一CMU助理教授Marijn Heule他們把這串代碼輸入40臺電腦組成的計算集群，30分鐘後，計算機給出了一個200GB大小的證明結果：凱勒猜想在不超過7維的空間上都是正確的。
  • 困擾數學家90年的猜想，被計算機搜索30分鐘解決了
    就連困擾人類90年的數學猜想也擋不住。來自斯坦福、CMU等高校的4名數學家，將一個數學難題轉化成了對10億個結果進行「暴力搜索」。那麼，這4位數學家要證明的「凱勒猜想」到底是什麼？為何非要用計算機來證明？計算機證明的結果可靠嗎？
  • 「黎曼猜想」被證明? 學者:未看到有分量專家評價
    45分鐘證明演講中，有30分鐘介紹歷史長期關注人工智慧、機器學習領域的垂直媒體「機器之心」昨天全程記錄了阿蒂亞爵士在論壇上有關黎曼猜想的宣講直播。其實整個45分鐘演講中，阿蒂亞花了近30分鐘的時間介紹歷史：素數、黎曼猜想的歷史。中間他也開玩笑說，如果你解決了黎曼猜想，你會出名，但如果你已經是個名人，（解黎曼猜想）那就會有聲名狼藉的風險」。因此，可以看出，雖然已經89歲高齡，但阿蒂亞爵士一直在自己的領域努力著。也許，這其實也是阿蒂亞爵士今天想傳達的精神。
  • 林為幹:解開電磁學的「哥德巴赫猜想」
    該理論意義深遠，受到了同行們的重視，半個多世紀以來一直被國內外學者所引用，並對現代衛星通信等產生了重大影響。1994年仍有法國學者認為近代衛星廣播通信業所用的多模技術是由拉貢（Ragan）及林為幹提出來的，其發展的基礎是根據林為幹及庫恩（Cohn）的工作，此工作至今仍在發展。     一腔多模的理論，使林為幹在微波研究領域初露頭角。
  • 100萬美元獎金、159年難題 「黎曼猜想」或將揭開謎底
    這場被安排在德國當地時間9月24日上午9點45分到10點30分的演講也因此引起全世界數學家們的關注。「黎曼猜想」的證明到底有何重要性？為什麼最接近證明黎曼猜想的人是阿蒂亞爵士？「最難賺到100萬美元的方式」，這是世界範圍內的數學家們對證明「黎曼猜想」的戲稱，100萬美元則是美國克雷數學研究所在2000年為解出問題者開出的獎金價碼。
  • 數學家惲之瑋，證明高階猜想，被譽為數論領域30年來最大突破
    他最近再次獲得學術界關注，是因獲得 2020 年西蒙斯學者獎（Simons Investigators），儘管獲獎一事早已在各大科技媒體刷屏，但他本人對相關報導並未關注。對於獲獎，惲之瑋很低調，他告訴 DeepTech：「這次獲得的是一筆研究基金，並不是獎項。」西蒙斯學者獎由西蒙斯基金會設立，獎項旨在獎勵數學、物理、天體物理和計算機科學領域的傑出研究者。
  • 現場直擊:阿蒂亞挑戰「世紀難題」黎曼猜想
    「 他提出的證據依賴一個名叫Todd function的新函數，這個函數跟精細結構常數相關。精細結構常數是物理學中一個重要的參數，用來描述原子物理學中原子譜線分裂，但它本身到底是不是一個不變的常數還存在爭議。阿蒂亞說，他是在研究精細結構常數時「偶然撞上」黎曼猜想的證明的。
  • 100萬美元獎金、159年難題,「黎曼猜想」今天或將揭開謎底
    159年前，德國數學家黎曼在題為《論小於給定數值的素數個數》的論文中提出的「黎曼猜想」，一直以來被視作「純數學領域最重要的問題之一」，是一千多條數學命題成立的前提條件。這場被安排在德國當地時間9月24號上午9：45-10：30的演講也因此引起全世界數學家們的關注。「黎曼猜想」的證明到底有何重要性？為什麼最接近證明黎曼猜想的人是阿蒂亞爵士？「最難賺到100萬美元的方式」，這是世界範圍內的數學家們對證明「黎曼猜想」的戲稱，100萬美元則是美國克雷數學研究所在2000年為解出問題者開出的獎金價碼。
  • 【光明日報】林為幹:解開電磁學的「哥德巴赫猜想」
    該理論意義深遠，受到了同行們的重視，半個多世紀以來一直被國內外學者所引用，並對現代衛星通信等產生了重大影響。1994年仍有法國學者認為近代衛星廣播通信業所用的多模技術是由拉貢（Ragan）及林為幹提出來的，其發展的基礎是根據林為幹及庫恩（Cohn）的工作，此工作至今仍在發展。一腔多模的理論，使林為幹在微波研究領域初露頭角。
  • 我數學家證明了龐加萊猜想的30%(圖)
    據新華社北京6月20日電(記者仇琳俞錚)為百年數學難題龐加萊猜想做出奠基性貢獻的國際著名數學家　　漢密爾頓教授的這段錄像，是由美籍華人數學家、哈佛大學教授丘成桐在2006年國際弦理論大會上播放的。　　廣東中山大學教授朱熹平和中國旅美數學家、美國利哈伊大學教授曹懷東最近在《亞洲數學期刊》6月號上發表論文給出了龐加萊猜想的完整證明。　　兩周前，美國國家科學院院士漢密爾頓教授專門來北京與曹懷東教授討論龐加萊猜想證明的細節。
  • 華人數學家排行榜
    華羅庚在解析數論、矩陣幾何學、典型群、自守函數論、多複變函數論、偏微分方程、高維數值積分等廣泛數學領域中都作出卓越貢獻。由於華羅庚的重大貢獻，有許多用他他的名字命名的定理、引理、不等式、算子與方法。 華羅庚還根據中國實情與國際潮流，倡導應用數學與計算機研製。
  • 近60年的「向日葵猜想」獲得重大進展,完整的解決方案已經在望
    一個看似簡單的數學問題困擾了研究人員近60年，它就是「向日葵猜想」。這個問題最早是由匈牙利數學家保羅·埃爾德斯和英國數學家理察·拉東於1960年提出的，被稱為「向日葵引理」。引理這個術語本質上是指「迷你定理」，它是指已經被證明是正確的，但還不足以將其完全稱為定理的程度。