頂會最佳論文覆滅科學家們30多年期待：複雜度遠超預期_風聞

克雷西 發自 凹非寺

量子位 | 公眾號 QbitAI

三十多年來，在線算法一直被科學家寄予厚望，但一篇論文的誕生讓它走下了神壇。

它的目標，簡單來説就是在沒有完整數據的情況下，通過有限的信息提前找到最佳策略。

在我們的生活中，例如股票市場的即時交易分析，還有導航路徑的實時規劃，都有在線算法的身影。

不過沒有完整數據，就意味着性能將受到限制；因此科學家們一直期待它能突破數據的桎梏，達到更高的效率。

然而就在最近，來自微軟研究院、牛津大學等機構的研究人員在進行了一場實驗之後發現，這種算法的複雜度遠遠超過了人們的期待。

他們也憑藉着這篇論文，在今年的計算理論頂會STOC上獲得了最佳論文獎。

那麼，他們獲獎的這項研究，具體説了些什麼呢？

科學家們的“30年期待”

這裏我們需要先來了解一些背景知識。

和在線算法相對的，還有離線算法，它在開始處理之前需要先接收到所有的輸入數據。

由於預先掌握了完整數據，在同等的數據規模下離線算法顯著快過在線算法

想象一下，現在要從一系列數字中找出最大值，第一種情況是直接知道所有數字，另一種是比較完前面的數才知道後面的數字是多少，顯然第一種情況的速度更快。

於是離線算法的性能被看作是一個標杆，並衍生出了“競爭比”的概念。

而在過去的30多年裏，在線算法曾一度被寄予競爭比接近1的厚望。

具體的體現是，關於在線算法，學界有一個經典問題，叫做k-server問題。

k-server問題可以這樣來描述：

給定一個度量空間和位於該空間指定位置的k個服務器，在該空間的不同位置中會出現一系列請求。

對於每個請求，都必須選擇一個服務器來響應該請求。

如果服務器已經在請求的位置，它可以立即響應；否則，它必須移動到請求的位置。

而k-server問題的最終目標，是將所有服務器移動距離的總和最小化。

舉個例子，在一公路旁有若干家餐館，路上有k個空閒的外賣員，這些餐館可能隨時需要外賣員上門取餐，此時外賣員的調度就可以看做是一個k-server問題。

而在這個過程當中，無論是系統還是外賣員在真的接到訂單之前都不知道訂單出現的時間和位置，此時的問題是如何將所有外賣員取餐所走的路程之和最小化。

直到這篇論文發表為止，長達30多年的時間裏，在線算法一直被期待在解決所有k-server問題時，複雜度都不超過Θ(log k)。

（其中Θ表示漸進緊確界，可簡單理解為數量級相同）

但這篇論文的出現，讓這個期待被打破。

那麼，作者又是如何把這個期待證偽的呢？

複雜度遠超預期

注：本節中的對數符號log，如無特別説明，底數為2

遞歸構建圖度量空間

為了探究k-server問題的複雜度，作者構建了一個遞歸定義的圖度量空間（本質上也是k-server問題）。

作者首先構造一個簡單的度量空間M(0)，然後把多個M(0)按照循環的方式連成一個環M(1)，然後把多個M(1)連接成M(2)……以此類推，最終形成了一個可以分割成對稱的子結構的空間。

在這個度量空間上作者設計了一個隨機請求序列ρ，它會在對稱子結構之間交替選擇請求點，迫使在線算法在子結構間頻繁移動，而最優算法是固定在一個子結構。

之後，作者證明了在這個特殊構造的度量空間和請求序列上,任何確定性在線算法的預期消耗最低也要達到Ω(log²𝑘)。

而具體的證明，則採用了數學歸納法。

數學歸納法

數學歸納法雖然名字裏有個歸納，實質上卻是一種嚴謹的演繹推理。

它首先驗證結論針對序列中的第一項是否成立，然後假設對第k項也成立，接着，只要能證明對第k+1項也成立，結論就可以得到證明。

這個過程就像多米諾骨牌，只要推倒（k+1）一塊，其他的牌自然也會隨之倒下，這時同時確保第一塊有同樣的效果，整個體系就完備了。

舉個例子，我們知道數列{a(n)=n}的前n項和S(n)=n(n+1)/2，用數學歸納法證明過程如下：

首先n=1時，a(n)=1，S(n)=1(1+1)/2=1，結論成立

然後假設n=k時結論也成立，此時S(k)=k(k+1)/2

那麼，當n=k+1時，S(k+1)=S(k)+(k+1)即S(k+1)=k(k+1)/2+2(k+1)/2提取公因子(k+1)，這個式子又可以寫成(k+2)(K+1)/2此時n=k+1，n+1=k+2，結論依然成立所以S(n)=n(n+1)/2得證

任意度量空間消耗下限

而具體到這項研究，作者利用隨機性和對稱性定義了一個新的序列ρ(w)，並假設在度量空間M(w)中，對隨機的ρ(w)，確定性算法的消耗下限為Ω(w²)。

首先對於M(0)，確定性算法的消耗下限為1，此時結論成立。

然後試着將w推廣到w+1，構建出M(w+1)的度量空間，它包含兩條由多個M(w)組成的對稱路徑。

在請求ρ(w+1)上，假設此時位於左路徑，下一段位於左右路徑的概率各為1/2。

如果下階段位於右路徑，算法複雜度將會因為路徑切換而升高，不是低消耗。

而如果位於左路徑，由於路徑上都是一個個M(w)，所以新增部分的消耗下限就是Ω(w²)（此為歸納法假設）。

於是對於w+1段路徑，可以將每一段的消耗Ω(w²)累加，即為(w+1)Ω(w²)，結合Ω的定義，最終可以證明M(w+1)的最低消耗為Ω((w+1)²)，進而證明假設成立。

回到最初的度量空間

而作者構建的M(w+1)都是由6個M(w)組成，則M(w)的大小n=|M(w)|=O(6^w)，取對數得log|M(w)|=w·log6。

代入Ω(w²)中，得到在n點度量空間中，消耗下限為Ω((logn/log6)²)，而當n=k時，消耗下限則為Ω((logk/log6)²)。

而log6為一個2到3之間的常數，除以這樣一個數不會帶來結果的顯著改變，也就證明了k-server問題中消耗不低於Ω(log²k)的結論。

當k足夠大時，log²k顯然大於logk，因此在這樣的k-server問題中，實現O(logk)級別的低消耗是不可能的。

而此前人們一直認為可以用這樣的消耗解決所有的k-server問題，因此反例的出現便宣告了這一設想的終結。

論文地址：https://dl.acm.org/doi/pdf/10.1145/3564246.3585132

參考鏈接：https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/