k-server 猜想被证明,在线算法理论再下一城
minilek · x · 2026-09-15
理论计算机科学界迎来一波「开放问题被攻克」的集中爆发。Aaroth 在推文中列举了当天被解决的几个经典开放问题:
- k-server 猜想:Christian Coester、Elias Koutsoupias、Marek Zbysiński 提交论文《The k-server conjecture is true》,证明确定性在线算法在每个度量空间上都能达到竞争比 k,具体证明工作函数算法(work function algorithm)满足该界。
- Matroid Secretary 问题
- Matrix Spencer 问题(可能几周前已被解决)
证明思路:把工作函数表示为矩阵,用代数形式编码所有可行路径,最优代价中的 min/加法运算对应形式表达式的加法与乘法,每个工作函数值对应矩阵 k 列的行列式;请求到达时通过基变换与行替换更新表示,摊还分析基于一个更大矩阵上的势函数。
Aaroth 同时给出判断:我们正走向一个「没有开放问题」的世界,但这不意味着数学消失——有意思的工作将转向发现新问题和构建自洽的理论框架,定义清晰、公认有趣的问题不会存活太久。
所属事件:悬挂数十年的 k-server 猜想获完整证明(3 条相关)→
「研究」频道最新
- Adobe 与 UCLA 提出 Tev：用可验证进度奖励破解长程 Agent 训练难题 — jiqizhixin · 2026-11-02
- 老招新用：path tracing 加 portal 采样，64spp 噪点显著下降 — ssh4net · 2026-11-02
- Marcel Böhme 提出漏洞引导加固哲学：为何安全永远无法一劳永逸 — mboehme_ · 2026-11-02
- Perplexity 开源研究型基准 WANDR：500 任务、17 万条证据点 — thisguyknowsai · 2026-11-02
- AI 意识研究者:我们没有可靠方法判断 AI 是否有意识 — dioscuri · 2026-11-02
- 蚂蚁团队发布统一反伪造模型，AI视频鉴伪达96% — inclusionAI · 2026-11-02