可能是計算機理論領域十年來最大的突破

2021-02-24 環球科學

撰文 阿德裡安·丘（Adrian Cho）

翻譯 丁家琦

這幾天一直謠傳所謂的「複雜理論」（complexity theory）領域出現了數年一見的大進展，可能會給網際網路領域帶來新的曙光。這麼說沒錯——因為新的突破與網絡之間的比較有關，正可以應用於人與人之間的網際網路聯結。芝加哥大學的數學家與計算機科學家拉斯洛·鮑鮑伊（László Babai）發現了一種數學方法，可以用比之前少得多的步驟來判斷兩個網絡是不是完全相同的，不管這些網絡有多複雜或纏結。計算機科學界已經炸開了鍋，因為很多難以解決的問題最終都可以歸結到比較兩個網絡是否相同這一任務上。

「如果這一方法是對的，它可能會成為計算機理論領域十年來最重要的成果。」麻省理工學院的計算機科學家、博客作者斯科特·阿倫森（Scott Aaronson）說。

所謂複雜理論，從根本上說就是研究哪些工作可以很容易地用計算機完成，哪些工作不能的理論。在複雜理論中，最關鍵的事情是搞清楚隨著輸入數據的增長，解決一個問題所需的步驟會以什麼樣的方式增加。舉個例子：如果你想知道一個給定的數，比如983或105227是不是素數（即只能被1和它自己整除的數），那計算機所要進行的步驟隨著給定數字位數的增長就相對比較緩慢，大體上以類似n^2的速度增長（n為位數）。像n^2這樣的表達式被稱為多項式（polynomial），因此該問題就被稱為可以在「多項式時間」內解決，複雜度類別為P。

而另一方面，如果你想要把一個數，如21112331分解質因數，即分解成質數相乘的形式，到現在為止還沒有人找到一個可以在多項式時間內解決該問題的算法。因此，分解質因數被認為是一個更難的問題，被歸類到更寬範圍內的「NP」問題之列，即「不確定性多項式」（nondeterministic polynomial）問題。簡單來說，對於NP問題，隨著輸入數據位數的增加，所需步驟會呈指數式增長，如2^n，它增長得比n^2快得多（舉個例子，100^2隻等於10000，而2^100則超過了10的24次方）。

而現在，鮑鮑伊找出了一個新算法，將一個原本被認為屬於NP的問題變成了較為容易的P問題。問題是這樣的：無論是傳染流感的人群，還是與生物體發生相互作用的蛋白質，都可以抽象為一系列的點（計算機專業術語稱為「節點」，node），它們之間的相互關係則用連接點的直線（稱為「邊」，edge）來表示。由於節點可以被任意地拖來拖去，所以即使是兩個看起來完全不同的圖，其連接方式也可能是完全相同的（見下圖）。所謂的「圖同構問題」（graph isomorphism problem），其主要任務就是確定兩個圖究竟是相同的，還是不同的，而鮑鮑伊宣稱已經找到一種新的算法來解決這個問題。


圖同構問題中的任務，就是判定兩個看起來明顯不同的圖能否經過重組變得完全相同——就像圖中的兩個圖一樣。圖片來源：WIKIPEDIA COMMONS

此前，這個問題最好的解決方法是俄勒岡大學的數學家與計算機科學家尤金·盧克斯（Eugene Luks）在1983年提出的，他的方法所需要的步驟幾乎隨節點數目按指數增長，而鮑鮑伊的算法所需要的步驟只比多項式增長稍多一些。雖然在外行人看來「指數增長」和「多項式增長」差別不大，但對於計算機專家來說這個定性的區別卻是極為激動人心的。「假如結果真的成立，這就是計算機理論科學領域一顆閃耀的明珠。」在麻省理工學院計算機科學家阿倫森的博客中，有讀者這樣評論道。其他的博客裡也有讀者表示：「超級讓人激動！」

不過，出乎意料的是，儘管我們生活中到處都有網絡和圖，鮑鮑伊的新算法的應用範圍卻不會很大。阿倫森說，現有的算法已經可以非常快速地解決大多數圖的同構問題了，如果鮑鮑伊的新方法成立，也只是證明少數極為複雜的圖也能用高效的方法處理。複雜理論中最大的問題，是「NP」型問題是否真正不同於「P」型問題——研究者通常認為回答是肯定的，否則類似網際網路加密之類的技術就會變得極其易受攻擊，但到此為止還沒人能嚴格證明NP≠P，鮑鮑伊的成果連這個問題的邊都沒挨到呢。

那麼鮑鮑伊的新算法的意義在何處呢？阿倫森說，它真正的成就，是把一個關鍵問題從難題轉變成為了簡單問題。圖同構問題曾經一直被認為是一個非常古怪的問題：它是一個難題，但其本身一些特性又與一些簡單問題相關；而到了現在，鮑鮑伊直接把它變成了一個簡單問題。

當然，他的工作還得經過其他研究者的檢驗。他於11月11日在芝加哥大學做了一次報告展示他的算法，在24日還將再做一次。阿倫森說：「我們還得看看他的算法中的細節。要知道，即使是鮑鮑伊這樣的科學家，也是可能犯錯的。」

原文連結：http://news.sciencemag.org/math/2015/11/mathematician-claims-breakthrough-complexity-theory

轉載請聯繫newmedia@huanqiukexue.com，

給雜誌社打電話也行，010-85325810-804。

《環球科學》2015年11月號已經上市，點擊文末閱讀原文即可購買新刊

相關焦點

  • 量子科學,未來十年最大變量
    2019年11月，在針對「如果量子科技在可以預見的未來發生重大突破，量子計算機和量子網絡真的來臨，原來的區塊鏈理論和區塊鏈技術基礎，包括密碼數學，哈希函數，都可能發生根本性的動搖，還會波及到今天人們開始普遍關心的「數字貨幣、比特幣」，甚至央行「數字貨幣」的未來場景」的大背景下，朱嘉明又在廣州「華南理工大學」組織了一場關於「量子技術與區塊鏈」的研討會。
  • 朱嘉明:量子科學 未來十年最大的變量
    2019年11月，在針對「如果量子科技在可以預見的未來發生重大突破，量子計算機和量子網絡真的來臨，原來的區塊鏈理論和區塊鏈技術基礎，包括密碼數學，哈希函數，都可能發生根本性的動搖，還會波及到今天人們開始普遍關心的「數字貨幣、比特幣」，甚至央行「數字貨幣」的未來場景」的大背景下，朱嘉明又在廣州「華南理工大學」組織了一場關於「量子技術與區塊鏈」的研討會。
  • 量子科學,未來十年最大的變量
    2019年11月，在針對「如果量子科技在可以預見的未來發生重大突破，量子計算機和量子網絡真的來臨，原來的區塊鏈理論和區塊鏈技術基礎，包括密碼數學，哈希函數，都可能發生根本性的動搖，還會波及到今天人們開始普遍關心的「數字貨幣、比特幣」，甚至央行「數字貨幣」的未來場景」的大背景下，朱嘉明又在廣州「華南理工大學」組織了一場關於「量子技術與區塊鏈」的研討會。
  • 展望未來十年,探索可能實現的科學研究項目|人工智慧|計算機|機器...
    我們進行了一些預測，來探索在未來十年內在某些科學領域可能實現的研究項目。太空：宇宙中只有我們嗎？過去幾十年來，科學家們一直為此著迷，未來十年可能找到一些關鍵的解答線索。醫學是該技術具有廣闊前景的領域之一。從日常監控人體健康狀況的可穿戴健身技術到可感知生命體徵的電子紋身等領域，都有可能取得突破。此外，科學家們還設想將納米機器人植入血液，將抗癌藥物輸送到目標細胞，同時無損其他細胞。然而，由於機器人在血液內的毒性和影響，這在未來10年內不太可能實現。
  • 朱嘉明:量子科學,未來十年最大的變量
    2019年11月，在針對「如果量子科技在可以預見的未來發生重大突破，量子計算機和量子網絡真的來臨，原來的區塊鏈理論和區塊鏈技術基礎，包括密碼數學，哈希函數，都可能發生根本性的動搖，還會波及到今天人們開始普遍關心的「數字貨幣、比特幣」，甚至央行「數字貨幣」的未來場景」的大背景下，朱嘉明又在廣州「華南理工大學」組織了一場關於「量子技術與區塊鏈」的研討會。
  • 【專欄】朱嘉明:量子科學,未來十年最大的變量
    2019年11月，在針對「如果量子科技在可以預見的未來發生重大突破，量子計算機和量子網絡真的來臨，原來的區塊鏈理論和區塊鏈技術基礎，包括密碼數學，哈希函數，都可能發生根本性的動搖，還會波及到今天人們開始普遍關心的「數字貨幣、比特幣」，甚至央行「數字貨幣」的未來場景」的大背景下，朱嘉明又在廣州「華南理工大學」組織了一場關於「量子技術與區塊鏈」的研討會。
  • 又有新突破！量子領域的「光碟」行動，將點燃計算機的新春天
    人類最期待的科技發展隨著5G網絡、信息爆炸、雲存儲等等，多個有關通訊、網際網路、計算機關乎人類未來的多個尖端領域新名詞交集在一起的時候，人們開始有更多的憧憬。但事實上，在這三大尖端領域中，突破傳統計算機系統的天花板，面對海量信息處理時，依舊能從容應對，量子計算機系統及其優越的算法，似乎有天然的優勢。
  • 我國在超冷原子量子模擬領域取得重大突破
    中國證券網訊 中國科學技術大學和北京大學相關研究人員組成的聯合團隊在超冷原子量子模擬領域取得重大突破。中國科大-北大聯合團隊在國際上首次理論提出並實驗實現超冷原子二維自旋軌道耦合的人工合成，測定了由自旋軌道耦合導致的新奇拓撲量子物性。
  • 中國在量子計算機領域取得了一個裡程碑式的突破,超過美國?
    基於產業技術演進的角度，第一次量子產業浪潮誕生了包括雷射、半導體和磁共振成像等具有劃時代的重大科技突破。而隨著基礎研究帶來的技術突破，量子科技產業將會迎來第二次發展浪潮。 量子計算是基於量子力學的新型計算方式，在理論上具有經典計算無法比擬的巨大信息攜帶和超強並行處理能力。
  • 量子編程取得突破:量子計算機的第一種直觀語言
    在追求強大的量子計算機方面，最近已經取得了一些技術進步。目前，蘇黎世聯邦理工學院的計算機科學家已經在程式語言領域取得了重要突破：他們的量子語言是此類語言中的第一種，它與古典計算機語言一樣優雅，簡單且安全。
  • 馬化騰的提問:未來十年哪些基礎科學突破會影響網際網路科技產業?
    馬化騰的提問:未來十年哪些基礎科學突破會影響網際網路科技產業？ 那計算機的算力是否會增長停滯呢？答案是不會，因為後面有我看好的一些方向。 2. 異構計算大有可為 GPU在深度學習領域大放異彩之後，大家突然意識到我們並不需要更小更多的電晶體就可以實現成百上千倍的算力提升，我可以通過改變晶片的架構來增強特定任務的算力，而不再只是依靠通用的cpu計算。
  • 新賽道新突破！我國研製出全球神經元規模最大的類腦計算機
    該計算機使用了792顆由浙江大學研製的達爾文2代類腦晶片，神經元數量規模相當於小鼠大腦，典型運行功耗只需要350-500瓦，這是目前國際上神經元規模最大的類腦計算機。與此同時，團隊還研製了專門面向類腦計算機的作業系統——達爾文類腦作業系統，實現對類腦計算機硬體資源的有效管理與調度，支撐類腦計算機的運行與應用。
  • 量子領域重大突破:潘建偉團隊將力壓谷歌,量子計算機將出世
    近日有新消息表示，我國的量子領域有了新的突破，潘建偉院士的團隊在學術交流會上表示，在年內這個備受矚目的團隊將實現60比特量子計算，這也就意味著谷歌的53比特量子計算水平已經成為過去，潘建偉團隊將做到突破。
  • 量子計算機應該是一個重大突破,一個實驗成果一個理論突破
    量子計算和經典計算機一樣，研究已經很成熟了，相同點就是一個數據，兩種處理，但中間的邏輯鏈，理論完全不同。量子計算機應該是一個重大突破，一個實驗成果一個理論突破，所以超弦理論的完善是它不可缺少的，它並不意味著物理學達到真正的成熟。基本模型都是經典力學。實驗證據已經成為事實，就和牛頓力學一樣。問題是跟不上其他理論發展。沒辦法建立算符空間和微觀形式的轉化關係，或者讓微觀解釋宏觀運動。
  • 我國量子計算機誕生,比美量子計算機快多少?軍事領域有什麼用?
    文/行人量子科技是20世紀興起的一項高新科技之一，同時也是難度最大的科技，研究量子科技，能夠使我們更加充分的了解這個世界的本質。在人們的傳統認知當中，世界其實是由物質構成的，但是量子理論的出現，很有可能會推翻人們的這種傳統認知，將哲學上升到一個全新的高度上去。近些年我國也在研製自己的量子技術，經過我國科學家幾年的研究與努力，就在上個月，我國的量子計算機技術再一次得到了突破，我國自行研製的量子計算機「九章」誕生。
  • 它來了!我國量子計算機新突破
    12月4日，中國科學技術大學宣布，其潘建偉團隊與中國科學院上海微系統研究所、國家並行計算機工程技術中心合作，成功搭建了一個76光子量子計算原型「九章」，只用了200秒就解決了數學算法「高斯玻色採樣」。這一突破使中國成為世界上第二個實現「量子優勢」的國家，牢固確立了中國在國際量子計算研究領域的領先地位。
  • 量子計算機領域內第一種高級程式語言 Silq 誕生
    近日，蘇黎世聯邦理工學院的計算機科學界人士在程式語言領域取得了重要突破：計算機科學教授 Martin Vechev 與他的團隊設計出了量子計算機領域內第一種高級程式語言 Silq，它能夠像傳統計算機語言一樣簡單、安全又可靠。
  • 研究突破可能將智慧型手機變成量子計算機
    跨過這座橋為將筆記本電腦和智慧型手機變成超強大的量子計算機打開了大門。對指數未來感興趣？連接，下載免費的電子書，觀看主題演講或瀏覽我的博客。量子計算機將具有驚人的強大功能，比當今的狀態運行速度快上億倍。量子計算機將具有驚人的強大功能，其運行速度比當今最先進的硬體快數億倍，直到至少在特定條件下可以成為宇宙中最強大的計算機的DNA計算機出現為止。
  • 量子計算在化學應用領域取得突破
    現在人們普遍認為，量子計算機將大大推進的第一個學科是量子化學。量子計算機1982年，獲得諾貝爾獎的物理學家理察·費曼（Richard Feynman）觀察到，模擬和分析分子對於數字計算機來說是非常困難，以至於無法實現任何實際應用，其主要難度並不在於控制這種模擬的方程。事實上，它們相對簡單，幾十年來就已為人所知。
  • 谷歌團隊新突破，量子計算機模擬化學反應，再現黑科技
    近日，有國外媒體報導稱，谷歌AI量子技術研究團隊在量子計算機上完成了有史以來規模最大的化學模擬數據分析。據了解，這是量子計算機第一次參與到化學模擬反應中，該研究成果引起了計算機領域、化學領域和量子技術領域的轟動，並於本月28日登上了《Science》雜誌封面。