計算複雜性理論前沿：UG 猜想證明的新突破

計算複雜性理論前沿：UG 猜想證明的新突破

來自專欄人工智慧學習筆記

最近的一系列新證明，使理論計算機科學家離這個學科的一個偉大猜想更近一步。

1.向證明 UG 猜想更進一步

今年1月份在線發布的一篇論文，最近其他三篇論文結合在一起，使得UG猜想的證明向前邁出了實質性的一步。UG 猜想即 Unique Games Conjecture，該猜想是由紐約大學的計算機科學家 Subhash Khot 在2002年提出的。（註：UG 猜想提出時，Subhash Khot 正在普林斯頓大學攻讀博士學位。）

UG 猜想（是否存在某種對網路進行著色的有效方法）在過去的十五年中，這一猜想刺激了對泡沫幾何（geometry of foams）和選舉系統穩定性（stability of election systems）等多個話題的探索。 如果這個猜想能夠得到證明，其含義將遠遠超出網路頂點著色（network-coloring）。例如有些問題，我們需要它滿足儘可能多的約束條件，比如數獨中的各種規則或一群婚禮嘉賓的座位偏好等，我們都能夠找到這些問題的最優演算法。

以色列威茨曼研究所的理論計算機科學家 Irit Dinur 認為：「如果這個猜想是對的，一大類著色問題的複雜度就能被很好地解釋」。

然而，直到此論文發表之前，所有證明 UG 猜想的嘗試都失敗了。 與此同時，計算機科學家還曾暗示這個猜想實際上可能是錯誤的。

Dor Menzer 說：「有些人認為，證偽這個猜想只是一個時間問題。」Dor Menzer 是以色列特拉維夫大學的研究生，同時與 Khot 和同校的 Muli Safra 教授一起是前面四篇論文的共同作者（他們三人與 Dinur 以及來自耶路撒冷希伯來大學的 Guy Kindler 共同撰寫了其中的兩篇論文）。

隨著這項新工作的發表，舊有的思想似乎已經轉變了。 哈佛大學理論計算機科學家Boaz Barak 曾是這個猜想最激烈的懷疑者之一，但他說：「這是證明 UG 猜想正確性最有力的證據， 這項工作振奮人心！」

2.為計算複雜性尋找漂亮的解釋

Khot 在構建 UG 猜想時（那時他還是普林斯頓大學的一名普通的博士研究生），他的腦海里一直有一個明確的目標：更好地理解「圖著色」問題的計算複雜度。具體來說，就是對網路節點（按數學家的定義，或可認為是一個「圖」中的「頂點」）進行著色，使其相鄰的頂點不能同色。

理論計算機科學家已經知道，對於需要三種或三種以上的顏色進行著色的圖來說，尋找最優著色方案(即使用最少的顏色進行圖著色)的問題是 NP 完全的（NP-complete problem)。這是一大類計算複雜度問題，幾乎所有的科研人員都認為，我們無法為其找到高效的求解演算法。（當然，我們總是可以通過窮舉的方法，來找到合適的著色方案，但是當要著色的圖很大時，這樣蠻力的演算法是非常低效的。）

P（Polynomially）問題：可在多項式時間內得解的問題。

NP 問題：不一定在多項式時間內得解，但可以在多項式時間內驗證一個解的問題。只有 NP 問題才能找到多項式級的演算法。

NPC 問題：所有 NP 問題都可以約化（Reducibility）到 NPC 問題。目前尚無多項式級的有效演算法，計算的時間複雜度是指數級甚至是階乘級的。

經典的圖著色問題是一類 NP 完全問題（NPC 問題），沒有多項式的有效演算法。而對於 NPC 問題而言，隨著問題規模增長，計算時長會呈指數級甚至階乘級增長。

關於計算複雜度和 NPC 問題，可參考：http://www.matrix67.com/blog/archives/105

但如果你可用的顏色數量，比必要的顏色更多呢？ 比如你要處理一個用四種顏色著色的圖，但你卻可以使用100種顏色。 你是否可以使用更大的顏色表，來有效地對這些圖進行著色？ Khot 認為答案是否定的，但他還無法證明。

Khot 發現，解決 Unique Games 問題的關鍵，在於理解圖著色的複雜度。圖著色問題的目標，和 UG 問題一樣，同樣是為圖中的點著色，但這個問題的規則更特殊：無論何時，為某個節點著色時，相鄰的節點都必須使用某種特定的顏色。而 UG 問題中，相鄰節點的著色規則可能會衝突（比如婚禮上的衝突的座位需求），所以，我們的目標是，找到一種著色方案，使之滿足儘可能多的著色規則。 （Unique Games 這個名字來源於博弈論中的一個類似的問題，而不是圖著色的問題）

對於 A 中給出的約束規則，可以找到一個滿足所有規則的著色方案，如 B。

但有時只能找到滿足部分約束規則的著色方案。比如對於 C 中給出的約束規則，可以找到著色方案 D，滿足了加粗連邊以外三條邊的約束規則（滿足75%的規則）。

乍看之下，如果圖上的著色規則能接近完全滿足約束規則，那麼找到一種完全滿足約束規則的著色方案應該不難。比如某個著色方案在99%的節點上可以符合規則地著色，那麼，似乎只要找到能讓剩下1%的節點成功著色的方法就可以了。

但 Khot 懷疑，即便已經有99%的節點可以著色，想要找到讓剩下1%節點成功著色的方案，也是非常棘手的。根本就沒有一種有效的演算法，可以為所有的圖都找到完全符合規則的著色方案。 他猜想，對於一套著色方案演算法，即使圖上99.9999％的節點都滿足著色規則，但要讓剩下0.0001％的節點也同時滿足，依然是困難的。不論這個比例有多小，都會是困難的。

Khot 提出這個猜想的動機與圖著色密切相關。但當他和其他理論計算機科學家開始對 UG 猜想做推廣時，他們發現它包含的信息遠超圖著色問題本身。 Khot 說，這個猜想是「自成體系的」。

特別是在 2008 年，加州大學伯克利分校的 Prasad Raghavendra 的工作表明，如果UG猜想是正確的，那麼一個叫做半定規劃（semidefinite programming）的演算法可以為所有的「約束補償問題」（constraint satisfaction problems，也就是說當你要儘可能滿足儘可能多的規則）提供最優的近似解。

你可以想當然地將演算法設計看作一個有創造性的過程，在這個過程中，你必須找到新穎的演算法去解決遇到的每個問題，」Barak 說道。 但是 Raghavendra 的工作意味著，如果 UG 猜想是正確的，那麼對於許多問題來說，創造性是多餘的——半定規劃演算法就是一種萬能的解決方案。

Irit Dinur：為很多事情找到漂亮的解釋，是我們的真愛所在，特別是在科學和數學方面。從這個角度來看，我們真的希望這個猜想是正確的。」

德州大學奧斯汀分校的 Dana Moshkovitz 認為，在 Raghavendra 的結果提出之後，理論計算機科學家對 UG 猜想的信任程度，「完全取決於我們是否相信半定規劃能夠如此強大，」得克薩斯大學奧斯汀分校的 Dana Moshkovitz 說道。 而對於許多理論計算機科學家來說，這似乎是一個可疑的命題。

他們的疑慮受到了 UG 問題的兩個特點的支持。 一方面，Khot 的猜想認為，對某些圖而言，即使找到讓99％節點滿足規則，但還是難以找到同時解決剩下的1％節點的著色方案。不過目前還沒有人能夠找到這樣的具體示例。 這與其他數學難題形成鮮明對比。 例如，當涉及到整數分解時（一個普遍認為沒有高效演算法的問題），只需將大素數相乘，就可以很容易地找出殘差分解演算法的數字。

2010年，Barak 與普林斯頓大學的 Sanjeev Arora 和瑞士蘇黎世聯邦理工學院的 David Steurer 一起為某些形式的 UG 問題，提出了「次指數」演算法（sub exponential algorithm）。

次指數演算法，指運算時間比多項式級增長得快，但仍明顯小於指數的演算法。

計算問題的蠻力方法往往帶來運算時間的「指數」級增長，可能是2^n或3^n。 例如，如果你想用3種顏色為n個頂點著色，那麼就有3^n種可能的著色——對於任何計算機來說，其耗時遠遠超過了可以接受的範圍，即便是對於很小的n也是如此。 在一個次指數演算法中，其指數小於n——例如它可能是n的平方根，這意味著該演算法比蠻力方法快得多。儘管還不夠快，不足以稱為是真正有效的（計算機科學家以使演算法的運行時間在多項式級別為榮，例如n^2或n^3）。

在 UG 問題的次指數演算法提出之後，「我想至於人們認為的演算法，得了，我們會加把勁研究，最終找到一個真正高效的演算法，」卡內基梅隆大學的 Ryan ODonnell 說道。要是這種情況發生，UG 猜想將會被證偽。

ODonnell 回顧了2014年在首爾舉行的國際數學家大會上午餐時，關於這個理論的非正式地投票。在那次會議中，Khot 被授予奈望林納獎（Rolf Nevanlinna Prize）——計算機科學最高榮譽之一——在很大程度上，是由於他的在 UG 猜想上做出的工作。而當 O Donnell 問誰認為這個猜想是對的時，只有他和 Khot 舉手。

O Donnell 說：「我覺得 Khot 因 UG 猜想獲獎的過程實在有趣，要知道很多人認為這個猜想是錯誤的」。

3.問題很難，但是可計算

四篇新論文（其中也依賴普林斯頓大學的 Barak，Steurer 和 Pravesh Kothari 的觀察以及 Moshkovitz 的觀點）所提出的觀點，並不能為 UG 猜想提供的完整證據。 不過，它證明了 「2-2 Games」 猜想，這是一種類似的猜想。所謂 「2-2 Games」，是指當你為一個頂點著色時，你可以從兩種顏色中選擇，為它的相鄰頂點著色。

但是，這一進展已經足以改變 Barak 關於 UG 猜想的想法。 「我不明白為什麼，這些猜想中的某一個是正確的，而其他的則是錯誤的，」他說道。

具體而言，Khot 對「2-2」問題的新證明為研究人員提供了證明 UG 猜想的途徑。 有一種簡單的方法可以將「2-2」圖變成 UG 圖——丟棄每個規則兩種顏色中的一個。 然後，如果你的著色能符合2-2的幾乎全部規則，則相同的著色可能會滿足你設計的 UG 約50％的規則。

由於這種關聯，擴展新的「2-2」證明並不困難。擴展新的「2-2」證明以表明在 UG 的設定中，如果你考慮所有可以滿足其至少49％著色規則的方式著色的圖（ 或49.9999，或者低於50％的任何數字），則沒有有效的演算法，能總是找到滿足規則1％或0.0001％或任何其他小數目的著色。 換句話說， UG 猜想已經被證明可以滿足近50％的規則，但尚未滿足幾乎全部規則的圖。

看到這項最新工作之後，ODonnell 認為趨勢正在轉變，但他認為像 UG 猜想這樣的問題還是很難解決的。

像 UG 猜想這樣的難題，現在用次指數演算法就能處理。在一些研究者看來，Khot 等人的工作最令人吃驚的一點是，他們找到了解決難題的可行方法。 計算機科學中的幾乎所有問題都可以歸為兩類：要麼可以靠一種高效的演算法快速解決，要麼得用蠻力、佔用大量計算資源的演算法才能處理。而 Khot 等人的工作表明，UG 猜想這類難題，介於這兩者之間。因為眾所周知的原因，一些研究者認為這樣的問題才是本質的。 「UG 猜想顯然位於這者之間的模糊地帶，」O』Donnell 說。

也許，最令 Khot 興奮的是，2-2 Games 猜想的證明，已經足以解決他研究生時曾著迷的原始問題的一個弱化版本，關於增加顏色選擇後是否可以有效地對圖形進行著色。 （答案基本上是否定的。）「我認為我在讀博士期間的夢想實現了」，Khot 說。

新論文中的許多重要思想都來自團隊中的研究生 Dor Minzer，他很有遠見卓識。 Khot 說：「Dor 這個傢伙很厲害，他才是整個工作的設計師。」

許多研究生可能對解決像 UG 猜想這樣著名而棘手的問題感到恐懼，但對於 Minzer 而言，這並不是一種顧慮。 「我的想法是，我有機會與我尊重的兩個人一起，思考一個有趣的問題，並且去看看會發生什麼，」他說道。

1月份的那一篇構成了 2-2 Games 猜想核心論證的論文，還沒有經過理論計算機科學界的徹底審閱。 但是像 Barak 和 Dinur 這樣的研究人員則確信其大方向是正確的。 Barak 說，論證中最具突破性的想法，在一篇更早的、他曾仔細檢驗過論文中出現過。

最近的論文「是一個極具參考價值的技術，但我的感覺是，最終它證明了一個非常可信的猜想，即使用這些工具......熟悉這個領域的作者會自然而然地這樣做的，」 他在一封電子郵件中寫道。 「我認為結論非常堅實。」

研究人員認為，新論文中最大的創新點是找到 Unique Games 問題與「Grassmann 圖」（即編碼高維空間之間交點的數學對象)之間的聯繫，但這可能仍不足以解決完整的 UG 猜想。 「但我認為這會讓人們更加樂觀地認為，我們可能會發現一條解決的路徑——UG 猜想的證明或證偽並不是那麼難以實現，」ODonnell 說。

一些研究人員預測，這條新路徑的發現，距離現在可能只是幾年，而非幾十年。 Barak 認為 UG 猜想算得上是可以持續一個世紀的問題，但在將來，它會得到解答。Khot 給出了一種很有希望的方法。

論文地址:

https://eccc.weizmann.ac.il/report/2018/006/

翻譯：王貝貝

審校：章彥博，劉培源

原文地址：https://www.quantamagazine.org/computer-scientists-close-in-on-unique-games-conjecture-proof-20180424/

推薦閱讀

複雜度閾值與概率論中的漏洞

神經網路與圖靈機的複雜度博弈

Nature最新論文解讀：最小車隊問題與「烏托邦」交通系統 | 張江

網路、幾何與物理 | 章彥博

加入集智，一起複雜！集智俱樂部團隊招新啦！

---

集智QQ群｜292641157

商務合作｜zhangqian@swarma.org

投稿轉載｜wangting@swarma.org

◆ ◆ ◆搜索公眾號：集智俱樂部

加入「沒有圍牆的研究所」

http://weixin.qq.com/r/NDsxKXDEti3JrTRK924m (二維碼自動識別)

推薦閱讀：