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

2023-12-3 22 12/3

複雜度不低於Ω(log²k)

任意度量空間消耗下限

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

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

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

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

顶会最佳论文覆灭科学家们30多年期待:复杂度远超预期

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

而如果位於左路徑,由於路徑上都是一個個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。

顶会最佳论文覆灭科学家们30多年期待:复杂度远超预期

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

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

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

顶会最佳论文覆灭科学家们30多年期待:复杂度远超预期

而此前人們一直認爲可以用這樣的消耗解決所有的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/