arXiv cs.AI· Jingwei Ge, Na Xie, Li Li, Jiayang Li·· 10 小时前AI 评分38
Goemans 不可分割流猜想:AI 辅助反例发现的解剖
Goemans's Unsplittable-Flow Conjecture: The Anatomy of AI-Assisted Counterexample Discovery
AI 导读
研究者提出一套正向反例构造流程,从不可能失败的树形结构出发加入进入终端的捷径弧,用冲突多面体给出需求、分数流与成本的精确条件,并据此刻画了 Rybin 通过 ChatGPT 找到的七顶点反例所支持的全部反例。实验中 ChatGPT 按该流程在 93 个其他有根树形结构上找到了有效构造,理论也解释了原反例为何难以靠盲目枚举发现。
正文 · AI 翻译
摘要:Goemans 曾猜想,任何分数单源流都可以转换为不可分流,且不增加总成本,同时使任意弧上的负载增加量至多等于最大需求。最近,Dmitry Rybin 宣布了一个通过与 ChatGPT 交互发现的七顶点反例,推翻了这一长期存在的猜想。然而,该交互并未揭示为何这一特定拓扑及其需求、分数流和成本选择能够共同奏效,该示例是否属于一个更广泛的族,或者哪些结构特征决定了反例可能出现的位置。它也未说明为何 AI 辅助搜索在早期人类努力未能成功的地方取得了成功。在本文中,我们开发了一条正向反例构造流水线。它从一个不可能失败的树形结构出发,并添加进入终端的捷径弧。由此产生的负载约束定义了一个有限的可行路径选择集合;它们的凸包,即冲突多面体,给出了需求、分数流和成本的精确条件。从一棵简单的树形结构出发,该流水线选择了 Rybin 的拓扑,并刻画了它所支持的所有反例。实验进一步证明了该流水线的可迁移性:当被指示遵循该流水线并改变初始树形结构和捷径放置位置时,ChatGPT 在真正不同于 Rybin 的拓扑上产生了反例,并从 93 个其他有根树形结构形状出发找到了有效构造。该理论还解释了为何原始示例难以通过盲目枚举发现,并表明 Rybin 的交互介于盲目枚举和完整的理论指导构造之间。
| 学科: | 机器学习(cs.LG);人工智能(cs.AI);组合数学(math.CO) |
| 引用为: | arXiv:2611.23244 [cs.LG] |
| (或 arXiv:2611.23244v1 [cs.LG] 用于此版本) | |
| https://doi.org/10.48550/arXiv.2611.23244 由 DataCite 颁发的 arXiv DOI |
提交历史
来自:Jiayang Li [查看电子邮件]
[v1]
2026年9月4日星期五 02:51:20 UTC(287 KB)
来源:arXiv cs.AI · arxiv.org