k-着色比计算色数更快

k-着色比计算色数更快
k-Coloring is Faster than Computing the Chromatic Number

arXivLabs 是一个允许合作者直接在我们的网站上开发和分享 arXiv 新功能的框架。与 arXivLabs 合作的个人和组织都认同并接受我们关于开放、社区、卓越和用户数据隐私的价值观。arXiv 致力于秉持这些价值观，且仅与遵守这些价值观的合作伙伴开展合作。您是否有能为 arXiv 社区增值的项目构想？了解更多关于 arXivLabs 的信息。

这篇 Hacker News 讨论聚焦于论文《K-着色问题比计算色数更快》，探讨了图着色的计算复杂性。虽然判定一个图是否为 $k$-可着色对于 $k \ge 3$ 的情况是 NP 完全问题，但用户们讨论了 $k$-着色（判定问题）与寻找色数（最小的 $k$）之间的关系。参与者明确指出，虽然可以通过二分查找利用 $k$-着色算法得出色数，但其效率取决于算法的复杂性，以及 $k$ 相对于 $N$ 是否较小。讨论中的很大一部分转向了在数学研究中使用大语言模型（LLM）的风险。批评者担心大语言模型会生成自信但错误的证明，而同行评审可能会漏掉这些错误，因此建议将机器验证的形式化方法作为标准做法。对话还涉及了关于职业环境中风险厌恶的更广泛的哲学争论，以及对人工智能生成的摘要与人工核对之间依赖性的讨论。最后，一位用户分享了他们自己的相关研究，为原始论文中讨论的复杂性参数提供了更紧密的界限。

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

k-着色比计算色数更快 k-Coloring is Faster than Computing the Chromatic Number

k-着色比计算色数更快
k-Coloring is Faster than Computing the Chromatic Number