每日 Arxiv

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

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

Created by
  • Haebom

作者

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

大纲

本文探讨了如何利用人工智能技术发现新的组合结构，以改进现有高效算法的局限性。具体而言，我们使用 AlphaEvolve（一个 LLM 编码代理）研究了最大割集 (MAX-CUT) 和最大独立集 (MAX-Independent Sets) 的平均情况难度，以及最大k割集 (MAX-k-CUT) 的最坏情况近似难度。由此，我们改进了最大割集 (MAX-CUT) 和最大独立集 (MAX-Independent Sets) 认证算法的上下界，并获得了最大4割集 (MAX-4-CUT) 和最大3割集 (MAX-3-CUT) 的新的非近似概率结果。此外，我们提出了一种利用 AlphaEvolve 有效改进验证流程的方法。

Takeaways，Limitations

•
Takeaways：
◦
利用人工智能技术（AlphaEvolve）产生突破现有算法界限的新成果。
◦
MAX-CUT 和 MAX-Independent Set 的边界改进。
◦
我们为 MAX-4-CUT 和 MAX-3-CUT 提出了新的非近似可行性结果。
◦
提供评估人工智能如何促进证明发展的标准。
•
Limitations：
◦
验证 AlphaEvolve 生成​​的结果需要花费大量时间。
◦
MAX-3-CUT 结果低于最佳性能（与自定义 PCP 方法相比）。
👍
Made with Slashpage