每日 Arxiv

本页面整理了世界各地发表的人工智能相关论文。
本页面使用 Google Gemini 汇总而成，并以非盈利为基础运营。
论文版权归作者及相关机构所有，分享时请注明出处。

组合结构的强化生成：复杂性理论的应用

Created by
  • Haebom

作者

安什·纳格达、普拉巴卡尔·拉加万、阿卜拉迪普·塔库塔

大纲

本文探讨了如何利用人工智能 (AI) 发现新的组合结构，从而改进高效算法的局限性。具体而言，我们使用 LLM 编码代理 AlphaEvolve 研究了 MAX-CUT 和 MAX-Independent Set 的平均情况难度，以及 MAX-k-CUT 的最坏情况近似难度。利用 AlphaEvolve，我们获得了 3 和 4 正则图的 MAX-CUT 和 MAX-Independent Set 认证算法的近似最优上界和下界，并发现了新的小工具约简方法，从而获得了 MAX-4-CUT 和 MAX-3-CUT 的新的非近似结果。

Takeaways, Limitations

•
使用 AlphaEvolve 为 MAX-CUT 和 MAX-Independent Set 设置新的边界。
•
使用 AlphaEvolve 改进 MAX-4-CUT 和 MAX-3-CUT 的非近似结果。
•
通过改进通过 AlphaEvolve 发现的配置的验证过程来降低计算成本。
•
MAX-4-CUT 结果略微提升了当前最佳结果，但 MAX-3-CUT 结果没有跟上现有的 SOTA。
•
AlphaEvolve 生成​​的候选结构的验证成本很高（需要花费指数级的时间）。
👍
Made with Slashpage