組合結構的強化生成：近似難度

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]。（這些上界通過解析方法1推導得出。）綜合上下界結果，我們幾乎完全解決了這些問題2。

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)方程?3?（形式為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輔助數學發現的作用時，我們至少需要考慮以下幾種情形：

1. 調用語言模型來總結某一領域的既有成果，規劃通往新定理的研究路徑，或直接生成（部分乃至完整）證明；
2. 使用AlphaEvolve等由AI衍生的工具來生成更優的證明構件（如gadget、圖結構）；
3. 使用獨立于AI的定制代碼來發現更優的證明構件；
4. 通過手工方式發現相同或更優的證明構件；
5. 上述（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種可能），但驗證任一候選解的正確性僅需2、23、112次按位乘法。即便驗證速度極快，AlphaEvolve仍未能找到H???×???的構造；事實上，我們甚至未能讓AlphaEvolve復現H???×???的構造——該階數曾是此前未知構造的最小階數，直至[KTR05]給出解法；而428階的構造方案其實早已公開于互聯網。

展望未來，LLM推理能力的進步 [LL25, GWD+25, Wei25] 或可與AlphaEvolve相結合，特別是在生成初始代碼片段以及對AlphaEvolve所用LLM進行更有效的問題定制化提示方面。我們將這些問題的探索留待未來研究方向。

原文鏈接：https://arxiv.org/pdf/2509.18057v6