出典:arXiv · cs.AI原文を見る ↗
原文の著作権は出典元に帰属します。当サイトでは収録、翻訳、体裁調整のみを行います。
事実関係
arXiv:2608.11211v1 Announce Type: new Abstract: Conway's 99-graph problem asks whether a strongly regular graph with parameters exists. We report a systematic, fully reproducible attack by an autonomous AI
解説と影響
强正则图是一类具有高度对称性的图,其参数 (v,k,λ,μ) 分别表示顶点数、每个顶点的度数、任意相邻顶点对的共同邻居数,以及任意不相邻顶点对的共同邻居数。Conway 的 99-图问题所问的,正是参数取 (99,14,1,2) 时这样的图是否存在。由于该问题的搜索空间极为庞大,传统方法长期未能给出确定答案。此次研究的关键在于引入「强制结构约简」策略,即在搜索过程中识别出某些必然出现的局部结构,据此压缩搜索空间,同时生成可验证的上下界,使结果不依赖于对 AI 推理过程的盲目信任。论文摘要强调该攻击是「系统性的、完全可复现的」,这意味着研究提供了可独立核验的计算路径。至于 AI 系统最终是否彻底解决了存在性问题,摘要未给出明确结论,仅表明给出了约简与界限。来源:arXiv
这一工作与同期发布的多篇 AI 系统研究形成互文。例如,关于多 LLM 智能体动态治理的研究讨论了目标函数缺失时智能体间交互的协调问题,而 99-图研究则展示了单一自主 AI 在明确数学目标下进行长程搜索的能力。来源:arXiv 另一项关于量化混合专家模型中路由损伤检测的研究,同样关注数值扰动对系统行为的影响,与图论搜索中对计算精确性的要求有相通之处。来源:arXiv 不过,这些素材均未直接涉及 99-图问题的数学细节,仅可作为同期 AI 研究生态的背景参照。
从方法论角度看,该研究的价值可能超越图论本身。传统上,数学猜想的计算验证常受制于两点:一是搜索空间过大导致算力不可承受,二是黑箱式 AI 推理难以取信于人。本文提出的「强制结构约简 + 可验证界限」组合,试图同时应对这两个困难——约简降低算力需求,可验证界限则提供审计依据。若该方法经同行评审后成立,或可为其他组合数学与图论难题的计算辅助证明提供模板。但需注意,论文目前仅以 arXiv 预印本形式发布,尚未经过正式同行评议,其结论的可靠性有待后续验证。来源:arXiv
参考資料
出典原文
arXiv:2608.11211v1 Announce Type: new Abstract: Conway's 99-graph problem asks whether a strongly regular graph with parameters exists. We report a systematic, fully reproducible attack by an autonomous AI research agent, scored under the track's partial-credit metric. Our verifiable contributions are: (1) an exhaustive proof that no circulant graph on satisfies more than of the constraints ($33$ of difference-classes), with the same ceiling for the other abelian group of order ; (2) a forced-structure reduction: makes each neighbourhood a perfect matching and puts the outer vertices in bijection with non-matched neighbour-pairs, collapsing existence to a -regular graph on vertices, encoded for CP-SAT and validated by recovering the unique ; (3) a validated prescribed-automorphism orbit-existence framework (fixed-point-free and single-fixed-point actions, checked on and the Paley graph ), and (4) a best verified artifact at , with evidence that this is a robust frontier (fourteen distinct methods, none exceeding it) entangled with the open question, since any provable bound below is a non-existence proof.