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 猜想获完整证明(3 条相关)→
「研究」频道最新
- 小米 MiMo 提出 CodeSpecWeave:用相互依赖规格合成任务训练编程智能体 — XiaomiMiMo · 2026-11-02
- Mistral Large 4 短提示词从零写出量子化学 SCF 求解器并自建 3D 可视化 — MistralAI · 2026-11-02
- 谁把「用 AI 治愈癌症」讲得最具体？2025 年路线图正在成形 — iskander · 2026-11-02
- arXiv 论文证明 SGD 最优步长调度:单调递减的线性衰减是唯一极小极大最优解 — konstmish · 2026-11-02
- Karpathy 的 nanochat:100 美元从零训练出类 ChatGPT,星标近 6 万 — karpathy · 2026-11-02
- 读完 46 份资料后写出 Agent Evals 指南：自评 95 分的评测为何不可信 — blaizedsouza · 2026-11-02