k-server猜想获证明，多项理论计算机公开问题接连告破
naval · x · 2026-09-15
arXiv 新论文《The k-server conjecture is true》宣布证明 k-server 猜想：确定性在线算法在每个度量空间上都能达到竞争比 k，证明核心是工作函数算法（work function algorithm）。
作者将工作函数表示为编码所有可行路径的矩阵，最优成本中的 min 与加法对应形式表达式的乘加，每个工作函数值对应矩阵 k 列的行列式；请求到达通过基变换与行替换更新表示，摊还分析基于一个由坐标对构成的更大矩阵的势函数。
引发讨论的背景是近期多个公开问题接连被解决（k-server、Matroid Secretary、Matrix Spencer）。Aaroth 评论称我们正走向一个没有公开问题的世界，但数学不会消亡：有趣的工作将转向发现新问题与构建连贯的理论框架，而「公认的有趣且定义明确的问题」将不再长久存在。
所属事件:k-server 猜想被证明，在线算法理论迎来突破(2 条相关)→
「研究」频道最新
- 首个 UMI 数据集完成:采集比遥操作更快,但模仿机器人很累 — DominiqueCAPaul · 2026-09-16
- ApprenticeBench 基准：顶尖人类测试者首试仅 51%，agent 不必满分 — hhsun1 · 2026-09-16
- 仅 1300 块 H200 加自建实验闭环，Periodic 训出 Neon 在材料科学基准上超越 GPT-6 Astra — vwxyzjn · 2026-09-16
- 新论文:OPD 推理后追加 RL 阶段,效果胜过纯 OPD 与纯 RLVR — gregd_nlp · 2026-09-16
- 视网膜影像可提前数年预测房颤风险，覆盖约 9 万人队列 — EricTopol · 2026-09-16
- 首个用私有基准双盲评测闭源模型的项目落地 — KLdivergence · 2026-09-16