k-Coloring 比计算色数更快
k-Coloring is Faster than Computing the Chromatic Number
图论领域迎来重大突破，Or Zamir 证明了针对 n 个顶点的图，k-Coloring 问题存在一种随机算法，其运行时间为 (2−ε_k)^n。此前，只有 k≤6 的情况已知拥有比通用 O⋆(2^n) 算法更快的解法，而该通用算法由 Björklund 等人提出用于计算色数。这项研究通过推广并组合 (k+2)-coloring 到 k-list-coloring 的归约工具，以及基于超图容器的方法，成功解决了这一长期悬而未决的难题。新的算法策略混合了长列表和短列表的实例，实现了从 (k+1)-list-coloring 到 k-list-coloring 的可迭代归约，为固定调色板下的列表着色问题提供了全新视角。
我们证明了 n 个顶点的图上的 k-Coloring 问题存在一种运行时间为 (2−ε_k)^n 的随机算法，其中对于每个固定的 k，ε_k 均大于 0。
HN 评论区
23- emil-lp
给不熟悉背景的朋友解释一下：
K-染色是指图可以用 k 种颜色染色，且任意两个相邻节点颜色不同。K-染色问题是一个判定问题，即回答“是”或“否”。
图的色数是指能实现 k-染色的最小 k 值。
显然，如果你有一个算法能解决其中一个问题，就能解决另一个。
这里的问题是：计算 k-染色是否比计算其最小（实际）k 值（即色数）更快。
森林、树和二分图都是 2-可染色的。平面图是 4-可染色的。但判断一个平面图的色数是否为 3 是 NP 完全问题。
还有一个非常有趣的未解猜想，即哈德维格猜想（Hadwiger's conjecture），它本质上说色数等于团（minor）数（不管那是什么意思）。
- black_knight
在 Brev 论文末尾有一个关于大语言模型（LLM）使用的章节。
现在，这篇论文将接受同行评审。因此，一旦发表，我们将像信任其他已发表的数学成果一样信任其结果。然而，虽然人类并非完美无缺，但 LLM 倾向于输出看似正确却充满自信的内容。因此，当 LLM 被这样用于生成证明时，我深感担忧。同行评审并不完美，可能也无法针对 LLM 特有的错误模式进行调整。
对此有一个解决方案，即对结果进行形式化并实现机器验证。对于 LLM 而言，我认为这将成为未来的最佳实践。
- drivebyhooting
快不了多少。
任何复杂度为 F(n) 的 k-染色算法，都可以通过对 N 进行二分搜索，转化为复杂度为 lg(N)F(N) 的色数算法。