一篇新論文利用 AI 生成的證明，解決了競爭分析中的一個基本問題，即 k 伺服器猜想。作者證明了工作函數演算法在任何度量空間上都能達到 k 的競爭比率。這個結果非常重要，因為 k 伺服器猜想被稱為競爭分析的「聖杯」，是理論計算機科學中的一個重大開放問題。其解決方法對用於快取、負載平衡和網路資源分配的線上演算法產生了影響。該證明依賴於將工作函數表示為矩陣的自然代數形式，該矩陣編碼了到達配置的所有可行路徑。這種方法確認了確定性線上演算法可以達到最佳的 k 競爭比率。

事件背景

k 伺服器問題是線上演算法中的一個核心問題，其中一組 k 個伺服器必須在不知道未來請求的情況下，在度量空間中移動以服務到達的請求。競爭分析通過將這些線上演算法的成本與最佳離線演算法的成本進行比較來評估其性能。該猜想認為工作函數演算法是 k 競爭的，即其成本最多是最優解的 k 倍。

社群觀察

社群強調了該結果的重要性，有些人回憶起證明相關界限（如 2k-1 競爭性）的歷史難度。人們還熱烈討論了 AI 在數學中的作用，指出其在驗證複雜證明和識別有前景的問題領域方面的優勢。