Kevin Pratt 论文称突破图 k-染色的 $2^n$ 时间界
rrwilliams · x · 2026-08-04
Kevin Pratt 提出图 k-染色的 $2^n$ 突破算法
这篇 arXiv 论文声称：对任意 $k$，图 $k$-染色都可以用一个带单侧误差的随机算法在 $O((2-\varepsilonk)^n)$ 时间内完成。
- 这意味着它突破了长期存在的 $2^n\cdot\mathrm{poly}(n)$ 时间界。
- 在此之前，已知能把指数基线进一步优化的结果只覆盖 $k \le 6$ 的情况。
- 论文还提到，Zamir 有一项独立同期工作。
「研究」频道最新
- AI 论文指出 best-of-K 提升的是生成表达能力 — anshulkundaje · 2026-08-04
- ASCII 艺术或许是前沿模型审美最好的基准 — weswinder · 2026-08-04
- 一份涵盖 DeltaNet、FlashKDA 和 MoE 的 AI 解释清单 — austinvhuang · 2026-08-04
- AI 指数在 2024 年末后陡增 5 倍，算力转向推理和后训练 — ProfBuehlerMIT · 2026-08-04
- 免费应用教你从零训练小模型，全部在本地 Apple MLX 运行 — dr_cintas · 2026-08-04
- 作者称纯 VLA 未必需要强长程规划，VLM 已能补位 — m_wulfmeier · 2026-08-04