Reinforced Generation of Combinatorial Structures: Hardness of Approximation
组合结构的强化生成：近似难度
https://arxiv.org/pdf/2509.18057v6
摘要
基于人工智能的方法能否帮助我们在复杂性理论中取得进展？我们提供了肯定回答的证据，利用AlphaEvolve（一种基于大语言模型的代码变异智能体）在以下三个场景中获得了新成果：
a) MAX-CUT与MAX-独立集的平均情况难度：我们改进了Kunisky与Yu近期的工作，在随机3-正则与4-正则图上针对MAX-CUT与MAX-独立集的验证算法，获得了接近最优的上界与（条件性）下界。我们通过构造顶点数多达163的近乎极值的Ramanujan图来获得改进的下界。此外，通过解析论证，我们将上界进一步加强，从而将这些问题的计算难度确定到小数点后第三位的误差范围内。
b) MAX-k-CUT的最坏情况近似难度：我们获得了新的不可近似性结果，证明在近似因子分别为0.987与0.9649的情况下，近似MAX-4-CUT与MAX-3-CUT是NP难的。该结果借助AlphaEvolve发现了新的小工具归约（gadget reductions）。我们的MAX-4-CUT结果优于当前最优的0.9883，而MAX-3-CUT结果优于目前基于小工具的最佳不可近似性结果0.9853，但尚未超越依赖定制化PCP（而非基于“标准”Håstad式PCP的小工具归约）所达到的最优结果16/17。
c) 度量旅行商问题（TSP）的最坏情况近似难度：我们证明在近似因子111/110内近似最小代价环游是NP难的，该结果通过AlphaEvolve发现了一个新的小工具，从而改进了此前117/116的最优结果。我们为3LIN(2)（一种常用于硬度归约的标准约束满足问题）到TSP的归约提供了模块化的正确性与完备性论证，这使得AlphaEvolve能够对有限约束图进行搜索。这种模块化方法可能对今后关于TSP不可近似性的研究具有独立价值。
我们面临的一项关键技术挑战在于：验证AlphaEvolve生成的候选构造代价高昂（有时需要与构造规模呈指数级的时间）。我们的成果得益于利用AlphaEvolve自身来演化出更快的验证过程（对我们的某些小工具而言，速度提升可达10,000倍）。这些结果表明，基于小工具的证明若经由AI工具处理，有望获得更强的结果。
1 引言
本文研究以下问题：基于人工智能的方法能否帮助我们在复杂性理论中做出新颖且非平凡的发现？我们通过在三个问题上取得的进展，为此问题提供了肯定回答的证据。
a) 稀疏随机图上MAX-CUT与MAX-独立集上界的验证难度。在第2节中，我们改进了[KY24]中提出的组合结构，在{3,4}-正则情形下获得了更优的下界。作为补充，我们还得到了新的上界，改进了Hoffman的经典谱界[Hof03, Hae21]。（这些上界通过解析方法¹推导得出。）综合上下界结果，我们几乎完全解决了这些问题²。
b) MAX-k-CUT的近似NP难性。在第3节中，我们针对k∈{3,4}的情形，给出了基于小工具的归约（源自标准的Håstad型PCP [Hås01]），用于证明MAX-k-CUT的近似NP难性。对于MAX-4-CUT，我们将当前最优的不可近似性结果从0.9883 [AOTW14]改进至0.987；对于MAX-3-CUT，我们将当前最优的基于小工具的不可近似性结果从0.9853 [KKLP96]改进至0.9649。我们的MAX-3-CUT结果介于两项使用定制化PCP的工作之间：[GS09]的0.9696与[AOTW14]的0.9411。
c) 度量旅行商问题（TSP）的近似NP难性。在第4节中，我们给出了一个新的基于小工具的归约（源自标准Håstad型PCP [Hås01]），用于证明度量TSP的近似NP难性。我们将当前最优结果117/116 [CC20]改进至111/110。这一改进推进了该问题硬度结果的长期研究脉络：[PY93, 1+δ]（未给出δ的显式值）、[Eng99, 5381/5380]、[BHK+00, 3183/3182]、[PV06, 220/219]、[Lam14, 185/184]、[KLS15, 123/122]、[CC20, 117/116]。附带说明，我们基于AI的探索仍在进行中，该界有望进一步改进。
值得注意的是，我们的结果均依赖于单一的（AI衍生）技术——AlphaEvolve [NVE+25, RPBN+24]，用于发现并验证优于先前构造的有限组合结构。在高层次上，AlphaEvolve利用大语言模型（LLM）迭代演化生成组合结构的代码片段（我们有时称之为“构造”），并依据某种标准对这些结构进行质量评估。尽管我们通过AlphaEvolve生成的结构均为有限构造，但借助适当的“提升”（lifting）[KY24, TSSW00, CC20]论证，我们的主要结果（定理2.1、3.1与4.1）均蕴含了对问题规模n的全称量词∀n。至少，我们的工作表明，我们应当常规性地将基于小工具的证明送入“AI优化”阶段。我们按人类参与程度（为使问题适配AlphaEvolve所需）递增的顺序呈现这些结果。
在操作层面，该系统包含三个组成部分：a) 用于构造组合结构的代码片段（C）；b) 用于验证并评分所生成结构的评估函数（称为验证器）；c) 基于先前C的集合与构造历史，建议新代码片段Cnew的大语言模型。通过对LLM进行提示，目标是引导Cnew生成更优的结构。（附录A提供了AlphaEvolve的更详细概述。）
AlphaEvolve的有效性在根本上取决于验证步骤，后者进而决定了搜索空间的形态。由于我们在庞大的搜索空间中寻求极值结构，对构造进行快速验证（包括评分）有助于AlphaEvolve尝试大量组合结构，并从中学习模式以剪枝搜索空间。我们最终为各问题找到的结构规模，与验证速度直接相关。
在AlphaEvolve中加速验证：这些问题所寻求的组合结构基于无向图。尽管对TSP下界及稀疏随机图上界验证的暴力验证速度尚可接受，但对MAX-k-CUT而言，验证则显著更具挑战性。下文将对此进行更详细讨论。
对于TSP，所发现的某个小工具包含20条边（分布在12个顶点上）以及大量约束条件（约11!条）以完成成功验证。因此，我们需要精心编写一个高速验证器，使其运行时间控制在约一秒之内。
2 随机图上的认证问题难度
我们在附录B.2中证明了该结果。为便于参考，我们整理了与先前结果的对比（见表1）。值得注意的是，我们获得了与匹配的上下界，其绝对误差仅0.005，因此定理2.1和2.2在这些情形下近乎最优。特别地，这激发了一个令人振奋的可能性：通过研究定理2.1和2.2的证明，或许能够获得关于的完整刻画。
关于使用AlphaEvolve寻找近乎最优下界的评述。本节以定理2.1的方法论及结果作为结语。文献[KY24]中针对d∈{3,4}给出的构造是顶点数不超过12的图，这些构造通过计算机辅助实验生成。我们通过随机采样大量正则图成功复现了他们的结果，尽管在构造中对自环数量存在事后认知。
改进它们的下界需要在更多顶点上进行构造，因为 MC(G) 或 IS(G) 的粒度受限于 G 的大小。在我们目标规模下，随机采样构造的方法行不通，原因有二：（1）d-正则 n 顶点图的空间呈组合爆炸式增长，意味着随机采样无法找到有趣的"极值"图；（2）计算 MC(G) 或 IS(G) 的复杂度关于 n 是指数级的，因此甚至很难为某个构造计算这些边界。
3 基于 Gadget 的 MAX-k-CUT 近似 NP-难性
近似算法领域 [WS11] 关注为计算困难的组合优化问题寻找近似最优解。在近似难性 [AB09] 中，主要目标是理解这种近似何时在计算上是困难的。我们在研究充分的约束满足问题（CSPs）框架内开展工作。
在 Max-CSP 设置中，输入是特定 CSP 实例 I 的描述，目标是计算可以满足的约束的最大数量。换句话说，我们试图近似计算函数 。通过引入 (c, s)-近似的概念，将近似问题转化为判定问题是很有用的，如下所示。
与先前不可近似性结果的比较。据我们所知，当前MAX-4-CUT的最佳困难性因子是85/86 + ε [AOTW14, 定理1.2]，我们通过定理3.2将其改进到0.987。[AOTW14]中的困难性是通过从MAX-3-CUT到MAX-k-CUT（对所有k > 3）的归约获得的。至于MAX-3-CUT，我们将定理3.1中的结果与三项工作[KKLP96, GS09, AOTW14]进行比较，这些工作为MAX-3-CUT获得了逐步更强的NP困难性结果。我们在定理3.1中的55/57 + ε不可近似性比率击败了[KKLP96]的67/68 + ε和[GS09]的32/33 + ε。我们的结果不足以击败Austrin、O'Donnell、Tan和Wright [AOTW14]使用从Label Cover的定制归约获得的16/17 + ε的最新技术。相比之下，我们的结果不需要任何新的PCP机制，仅利用Håstad的经典PCP [Hås01]。我们不了解限制基于gadget的方法击败[AOTW14]不可近似比率的根本性障碍，可以想象，从不同的源问题到3LIN(3)的基于gadget的归约可以实现这一点。
3.1 为可靠性和完备性保证开发搜索框架
为了将AlphaEvolve应用于这个问题，我们开发了一个基于gadget归约论证的模板，并分离了该论证中对gadget所需的性质（详见定义C.1和定理C.2）。我们通过候选gadget的最终性能来评分，即通过将定理C.2应用于候选gadget所隐含的不可近似比率。
为MAX-3-CUT找到的所有gadget中，每条边有0到3个副本。这是意料之中的，因为许多先前结果中找到的最优gadget（例如 [TSSW00, HHM⁺17]）都包含小的整数权重。因此，我们得到了一个简洁的不可近似比 55/57。
寻找MAX-4-CUT的gadget。 我们寻找MAX-4-CUT gadget的过程与之前的主要区别在于，我们必须在变量更多的gadget中进行搜索（多达19个变量），因此我们需要一个性能极高的验证器实现（同样，我们将在第3.2节详细阐述）。即使有了这个优化后的验证器，评估速度仍然相当慢，评估一个19变量的gadget大约需要一秒钟。因此，AlphaEvolve花了更长的时间才找到一个搜索算法，该算法在给定这个优化验证器的情况下，能够找到任何非平凡的gadget。AlphaEvolve最终产生的搜索算法具有一个独特的特性：它在带权gadget中进行搜索，权重为实数值，经过适当的缩放和舍入后，得到的gadget权重在1到1429之间变化很大。
3.2 通过AlphaEvolve实现更快的验证以探索更大的Gadget
寻找大型gadget的主要挑战在于，对gadget进行评分的成本随变量数量呈指数级增长；计算定义C.1中描述的完备性和可靠性参数本质上相当于求解一个MAX-k-CUT实例，这需要指数时间。即使对于，当使用暴力MAX-3-CUT验证器搜索规模仅为11的gadget时，AlphaEvolve的速度也会显著下降。
这个问题没有现成的解决方案，即不存在已有的快速验证器；现有的SMT/MIP求解器 [ES03, MML14] 也不太可能被改造用于求解MAX-k-CUT。为了解决这个问题，我们使用AlphaEvolve本身来加速一个朴素的暴力MAX-k-CUT实现，通过运行时间和正确性来对候选实现进行评分。为了计算运行时间，我们创建了一个综合数据集，包含来自20个随机模型的各种MAX-k-CUT实例，这些模型具有不同程度的植入结构。然后，我们要求AlphaEvolve最大化变量数 m，使得验证器在我们的数据集上求解规模为 m 的实例时，平均所需时间不超过一秒。
最大的挑战是确保AlphaEvolve不会作弊，找到一个快得多但不正确的验证器。如前所述，我们通过以下方式实现正确性：(1) 检查验证器在综合数据集上的正确性，(2) 使用一个独立的评判LLM来认证候选验证器的正确性。这些技术单独使用时都过于宽松，无法避免不正确的验证器，但通过人工检查我们发现，将它们结合起来就足够了。
我们注意到，一旦 m 足够大，就无法使用暴力实现（保证正确）为我们的数据集标注"ground truth"分数。相反，我们归纳地依赖AlphaEvolve之前产生的验证器的正确性（这些验证器已经通过了上述正确性检查），它们足够快，可以为较大的 m 提供标签。
3.3 与其他计算技术的比较
我们现在调研一些其他用于寻找gadget的计算技术，并讨论为什么它们在我们特定问题的规模上似乎是不可行的，即使是对于更简单的MAX-3-CUT设置。
最直接的比较是TSSW框架 [TSSW00]，它将寻找最优gadget的任务转化为一个线性规划（LP）。这样做主要困难在于计算gadget完备性时存在存在量词。为了消除这些量词，[TSSW00] 对gadget中的辅助变量进行规范化。结果，编码最优gadget的LP规模在源谓词的满足赋值数量上是双指数级的；对于从3LIN(3)到MAX-3-CUT的归约，这个数字是，这在计算上是不可行的。有时（正如我们MAX-3-CUT的 gadget的情况），可以论证并非所有辅助变量都是必需的，从而得到一个更易处理的LP，但不清楚这在非常特殊的情况之外是否可行。
如果希望将gadget中的变量数固定为小于336的某个特定常数（如我们gadget的14个变量），可以通过使用整数变量编码存在性约束，将线性规划（LP）改为混合整数规划（MIP）。例如，即使除一个存在性约束外其余全部消除，求解该MIP仍耗时10小时。（我们使用SCIP求解器 [BBB+24a, BBB+24b] 对问题进行直接编码。）因此，MIP方法在使用最先进（SOTA）求解器的情况下似乎也并不可行。
4 度量TSP近似计算的NP难性
这种MWST形式对难归约特别有利。通过将关注点从寻找简单回路转移到寻找最小成本的连通欧拉子图，可以避免显式构造度量闭包的繁琐任务。这使得归约能够在稀疏图上局部定义权重——通常给边分配小权重，给非边分配大惩罚——同时确保原始困难实例的结构性质得以保持。
我们使用AlphaEvolve寻找一个gadget（称为方程gadget）来改进从Hybrid-3LIN(2)到MWST的归约，同时保持其余论证不变。这立即将难近似因子从117/116改进到了111/110。
使用AlphaEvolve，我们发现了一个新的方程gadget（图4），其性能优于[CC20]中出现的（图8a）⁸。为了量化这一改进，我们现在更具体地描述方程gadget：每个3LIN(2)方程ℙ³₂（形式为x⊕y⊕z=1）被分配一个方程gadget，其中图4中的绿色顶点{1,2,3}（也称为接触顶点）对应变量{x,y,z}。红色顶点{4}被称为中心顶点，并在实例中所有3LIN(2)方程的方程gadget的所有出现中共享。方程gadget中的其余顶点（在图2中以蓝色显示）用于确保由满足的3LIN(2)方程和不满足的方程产生的生成环游的权重之间存在差距。黑色边（称为“非强制边”）在任何环游中都是可选的，而任何环游都必须至少经过每条红色边（称为“强制边”）一次。我们注意到，标准技巧（例如，[KLS15]）可用于实现强制某些边在MWST中被选取的约束。绿色虚线边称为特殊边，仅用于分析目的，在实际的MWST实例中不会出现。
如前所述，若方程gadget对生成环游的贡献在子句满足/不满足时分别较小/较大，则该方程gadget表现良好。在下文中，我们将这一要求提炼为关于该gadget的自包含陈述。给定一个方程gadget，我们考虑其中覆盖每个顶点的不相交环游集合。此类集合与(x,y,z)的特定赋值相关联，其中当且仅当变量对应的接触顶点与中心顶点4出现在同一环游中时，该变量被赋值为True。此外，除包含中心顶点的环游外，每个环游都会受到权重惩罚1。对于3LIN(2)方程的赋值(x,y,z)，我们将关注与(x,y,z)相关的任何此类集合的可能最小总权重（包括任何权重惩罚）。我们注意到上述描述是简化的，因为它未考虑与约简其余部分以不希望的方式交互的“不诚实”环游集合。为了处理这些情况，我们在形式化证明中采用略微不同的形式化方法，将讨论推迟到附录D.2。
我们对方程gadget的改进：AlphaEvolve找到的改进型方程gadget（图4）允许与3LIN(2)方程的满足赋值相关联的集合总权重为10，与不满足赋值相关联的至少为11，而[CC20]中的gadget分别为13和14。这立即改进了约简的性能，使MWST（以及等价的度量TSP）的不可近似比从117/116提高到111/110。我们新gadget的描述、完整约简以及作为方程gadget函数的最终不可近似比的证明在附录D中提供。
虽然我们在图4中展示了对应于谓词x⊕y⊕z=1的方程gadget，但我们可以使用对应于x⊕y⊕z=0的gadget（与[CC20]中的设置相同）获得相同的近似比。然而，该gadget更为复杂。我们将它的描述以及与[CC20]的并排比较推迟到附录D.3。
核心思想及AlphaEvolve的重要性：在本文讨论的问题中，TSP需要最多的人工参与，主要因为不存在现有的gadget约简搜索框架（类似于[TSSW00]用于MAX-k-CUT）。特别是，[CC20]中的完整约简包含方程gadget之外的脚手架，且约简的所有组件作为单个对象一起分析。在先前工作[CC20,KLS15]的证明结构中，似乎不清楚如何抽象出一组可验证的约束，使得AlphaEvolve可以单独用于搜索更好的方程gadget。在本工作中，我们将可靠性和完备性证明模块化，使其依赖于明确定义的可靠性和完备性参数，这些参数被定义为方程gadget本身的优化问题（定义D.4）。这种模块化对未来工作可能具有独立的研究价值。我们使用AlphaEvolve搜索方程gadget，以最大化从这些可靠性和完备性参数获得的最终不可近似比。
方程gadget搜索的优化问题可表述为混合整数规划（MIP）。由于其简单性，可以想见：若预先已知辅助顶点数量，图4中的gadget可通过直接求解该MIP得到。然而，由于对应x⊕y⊕z=0的方程gadget（图8b）涉及大量约束（约11!条），使用传统SMT/MIP求解器将面临与MAX-k-CUT问题相同（第3.3节所述）的计算瓶颈。
5 关于AI辅助数学与复杂性理论的讨论
在研究AI辅助数学发现的作用时，我们至少需要考虑以下几种情形：
- 调用语言模型来总结某一领域的既有成果，规划通往新定理的研究路径，或直接生成（部分乃至完整）证明；
- 使用AlphaEvolve等由AI衍生的工具来生成更优的证明构件（如gadget、图结构）；
- 使用独立于AI的定制代码来发现更优的证明构件；
- 通过手工方式发现相同或更优的证明构件；
- 上述（1）–（4）情形的组合。
文献综述：大语言模型（LLM）能够有效生成领域内既有文献的综述，这一观点已被讨论了一段时间 [WLNR23, WZLJ23, HLL+24, GUK+24]，我们的实际体验也通过多个提示验证了这一点。所得结果（除偶尔出现幻觉外）为更深入的探索与理解提供了良好起点。有趣的是，在诸多案例中，我们能够快速生成一个陌生领域的研究现状概览；我们相信，这一能力将日益被跨领域工作的科学家所采用，例如使代数学家能够迅速掌握拉姆齐理论。我们预计，随着时间推移，这将促进学科间更流畅的知识交融。然而，我们尚未能通过提示使LLM生成可用于获得新结果（如本文所报告结果）的可行研究计划，这正是更深层努力的焦点，例如Google的Co-Scientist计划 [GWD+25]。
直接提示：已有若干研究尝试通过直接提示LLM来为开放性数学命题生成证明 [Raa25, Bub25, OD25, DdMN25, JR25, BCE+25]，成效不一。在某些情况下，LLM确实能够生成先前未被证明命题的完整且正确的证明 [Bub25, BCE+25]（尽管坚持不懈的人类研究者或许也能推导出相同结果）；但在更多情况下 [Raa25, OD25, DdMN25, JR25]，LLM仅能生成证明草图，最终仍需人类补全。截至本文撰写时，该方向一项重要工作是 [BCE+25]。该报告记录了GPT-5在加速数学与理论计算机科学研究方面的能力，展示了“脚手架”技术——即通过更简单、相关的热身问题对模型进行预训练——如何使其推导出在线算法的改进界，并形式化证明了图论中先前开放的猜想。作者强调，该模型能够超越单纯的信息检索，成功构建出曾令人类专家束手无策的新颖反例与证明策略，例如为凸体追踪问题中的“Follow-the-Leader”算法生成复杂反例，以及提出解决Erdős问题[Blo]。
总体而言，当前这些证明/草图仍需人类验证其正确性。我们曾自然地尝试通过提示标准LLM直接生成本文中的组合结构，但均告失败⁹。尽管随着LLM推理能力的提升 [LL25]，这一目标未来或可实现，但正式比较已超出本文范围。我们强调，我们的构造始终附带可通过标准计算方法形式验证的正确性证书；一旦验证代码可靠，便无需进一步的人工审查。
展示AlphaEvolve的广度：近期论文 [GGSTW25] 全面展示了由LLM引导的进化搜索（AlphaEvolve）如何在分析、组合与几何领域中自主发现新颖数学构造，其成果令人惊叹——例如通过创造性地对验证用语言模型实施“提示注入”，找到了“四守卫”逻辑谜题的反例。该方法显著改进了诸如挂谷针问题与环加载问题等长期难题的界，且往往仅需极少问题定制调优，即可达到与人类设计基准相当甚至更优的结果。
近似难度中的计算方法：在随机图的平均情况难度与MAX-k-CUT的NP难度近似问题中，此前已使用过计算机辅助方法 [TSSW00, Hås01, KY24]。[KY24] 利用计算方法生成了具有较大割值（或独立集）的d-正则拉马努金图（d ∈ {3, 4}）。尽管他们未明确说明计算方法，但我们可通过随机采样d-正则图并暴力测试其性质来复现其结果。基于第2节所述原因，[KY24] 仅能对n ≤ 12证明其下界，而我们发现的图可达n = 163。
对于第3节中的NP难度gadget归约，可靠性和完备性约束均可通过斯科伦化转化为线性规划 [TSSW00]。然而，此类线性规划的规模随约束图顶点数呈双重指数增长。因此，即便是MAX-3-CUT问题，使用标准线性规划求解器处理 [TSSW00] 中典型变量数（≈336）的线性规划也已不可行。也可直接使用SMT/MIP求解器处理非凸规划，但当变量数n ≥ 14时，约束数量呈指数级增长，这些求解器同样难以扩展（详见第3.3节讨论）。在TSP近似难度问题中，可靠性和完备性约束亦可表述为MIP约束；即便方程gadget的顶点数适中（如图8b中的12个），约束数量也会变得极其庞大（约11! ≈ 3 × 10⁷），超出标准MIP求解器的处理能力。
手工设计gadget：理论上，人类专家或高度定制的计算验证器最终或许能发现这些解。然而，其发现很可能已超出简单“纸笔推导”方法的能力范围，且标准SMT/MIP求解器亦未能生成它们。此外，人类通常凭借对构造对象对称性的洞察来直觉性地裁剪搜索空间；而在我们的TSP gadget中，不对称性似乎是实现改进的关键。
AI与大量人力结合：我们的工作与 [Tao25] 均属于AI与显著人力投入相结合的范例。特别是，[Tao25] 记录了通过混合工作流快速解决Erdős问题 [Blo] 的过程：人类智慧引导多个AI系统——包括用于生成最优构造的AlphaEvolve，以及用于在Lean中进行形式验证的自动定理证明器Aristotle [ABB+25]。通过整合众包数学洞见、AI驱动的深度文献检索与计算发现，该协作在48小时内成功生成了解答。在我们的案例中，为使问题适用于AlphaEvolve，我们不得不（手工）重构度量TSP的证明逻辑。
秉承图灵模仿游戏 [Tur50] 的精神，对AI辅助数学发现稳健性的一项有力检验是持久性（durability）：即通过AI辅助获得的新成果是否会被人类（可能借助计算机辅助）迅速超越。我们注意到，某些AI辅助数学的成果事实上已被人类在不使用AI的情况下快速复现或改进 [Ger25, BSZ25]；在某些情况下，相关结果甚至早已存在（有时甚至在问题被明确提出之前 [Alo24, Rec25]），但在应用AI方法时作者并不知晓 [AM25, BCE+25]。
结语：尽管我们在此的经验有限且远非定论，但我们认为一些早期主题正在浮现。
首先，语言模型能够生成研究计划并总结领域现状 [GWD+25]。尽管我们尚未能借此直接推导出新颖结果，但这一能力使非专业人士能够快速学习新领域，我们预计这将促进更广泛的科学交叉融合。
其次，我们预计未来将出现越来越多“AI率先抵达”的证明，但往往缺乏“若无AI则无法完成”的明确证据。在所有这些案例中（且可论证地，在AI应用于科学的广泛场景中），验证环节将持续成为瓶颈。我们留待一个开放问题：直接提示LLM最终能否复现并超越我们的结果。
第三，我们的工作表明，基于gadget的归约方法适合采用AlphaEvolve进行超越传统方法（如SMT/MIP求解器）的优化。这反过来暗示，若要超越AlphaEvolve，通常需要采用非gadget方法，例如定制化的概率可检验证明（PCP）[AOTW14]。
最后，值得反思我们方法的一些失败案例。对于某些问题，即便验证极为简单，AlphaEvolve仍无法奏效。一个例子是Hadamard-668猜想，该猜想断言存在668×668阶的Hadamard矩阵（更一般地，猜想对任意4的倍数n均存在n×n阶Hadamard矩阵；668是目前尚未获证的最小阶数）。我们曾尝试用AlphaEvolve构造该矩阵。尽管搜索空间庞大（达2⁶⁶⁸²种可能），但验证任一候选解的正确性仅需2、23、112次按位乘法。即便验证速度极快，AlphaEvolve仍未能找到H₆₆₈×₆₆₈的构造；事实上，我们甚至未能让AlphaEvolve复现H₄₂₈×₄₂₈的构造——该阶数曾是此前未知构造的最小阶数，直至[KTR05]给出解法；而428阶的构造方案其实早已公开于互联网。
展望未来，LLM推理能力的进步 [LL25, GWD+25, Wei25] 或可与AlphaEvolve相结合，特别是在生成初始代码片段以及对AlphaEvolve所用LLM进行更有效的问题定制化提示方面。我们将这些问题的探索留待未来研究方向。
原文链接：https://arxiv.org/pdf/2509.18057v6
热门跟贴