Reinforced Generation of Combinatorial Structures: Hardness of Approximation

組合結(jié)構(gòu)的強(qiáng)化生成：近似難度

https://arxiv.org/pdf/2509.18057v6

摘要

基于人工智能的方法能否幫助我們?cè)趶?fù)雜性理論中取得進(jìn)展？我們提供了肯定回答的證據(jù)，利用AlphaEvolve（一種基于大語(yǔ)言模型的代碼變異智能體）在以下三個(gè)場(chǎng)景中獲得了新成果：

a) MAX-CUT與MAX-獨(dú)立集的平均情況難度：我們改進(jìn)了Kunisky與Yu近期的工作，在隨機(jī)3-正則與4-正則圖上針對(duì)MAX-CUT與MAX-獨(dú)立集的驗(yàn)證算法，獲得了接近最優(yōu)的上界與（條件性）下界。我們通過(guò)構(gòu)造頂點(diǎn)數(shù)多達(dá)163的近乎極值的Ramanujan圖來(lái)獲得改進(jìn)的下界。此外，通過(guò)解析論證，我們將上界進(jìn)一步加強(qiáng)，從而將這些問(wèn)題的計(jì)算難度確定到小數(shù)點(diǎn)后第三位的誤差范圍內(nèi)。

b) MAX-k-CUT的最壞情況近似難度：我們獲得了新的不可近似性結(jié)果，證明在近似因子分別為0.987與0.9649的情況下，近似MAX-4-CUT與MAX-3-CUT是NP難的。該結(jié)果借助AlphaEvolve發(fā)現(xiàn)了新的小工具歸約（gadget reductions）。我們的MAX-4-CUT結(jié)果優(yōu)于當(dāng)前最優(yōu)的0.9883，而MAX-3-CUT結(jié)果優(yōu)于目前基于小工具的最佳不可近似性結(jié)果0.9853，但尚未超越依賴定制化PCP（而非基于“標(biāo)準(zhǔn)”H?stad式PCP的小工具歸約）所達(dá)到的最優(yōu)結(jié)果16/17。

c) 度量旅行商問(wèn)題（TSP）的最壞情況近似難度：我們證明在近似因子111/110內(nèi)近似最小代價(jià)環(huán)游是NP難的，該結(jié)果通過(guò)AlphaEvolve發(fā)現(xiàn)了一個(gè)新的小工具，從而改進(jìn)了此前117/116的最優(yōu)結(jié)果。我們?yōu)?LIN(2)（一種常用于硬度歸約的標(biāo)準(zhǔn)約束滿足問(wèn)題）到TSP的歸約提供了模塊化的正確性與完備性論證，這使得AlphaEvolve能夠?qū)τ邢藜s束圖進(jìn)行搜索。這種模塊化方法可能對(duì)今后關(guān)于TSP不可近似性的研究具有獨(dú)立價(jià)值。

我們面臨的一項(xiàng)關(guān)鍵技術(shù)挑戰(zhàn)在于：驗(yàn)證AlphaEvolve生成的候選構(gòu)造代價(jià)高昂（有時(shí)需要與構(gòu)造規(guī)模呈指數(shù)級(jí)的時(shí)間）。我們的成果得益于利用AlphaEvolve自身來(lái)演化出更快的驗(yàn)證過(guò)程（對(duì)我們的某些小工具而言，速度提升可達(dá)10,000倍）。這些結(jié)果表明，基于小工具的證明若經(jīng)由AI工具處理，有望獲得更強(qiáng)的結(jié)果。

1 引言

本文研究以下問(wèn)題：基于人工智能的方法能否幫助我們?cè)趶?fù)雜性理論中做出新穎且非平凡的發(fā)現(xiàn)？我們通過(guò)在三個(gè)問(wèn)題上取得的進(jìn)展，為此問(wèn)題提供了肯定回答的證據(jù)。

a) 稀疏隨機(jī)圖上MAX-CUT與MAX-獨(dú)立集上界的驗(yàn)證難度。在第2節(jié)中，我們改進(jìn)了[KY24]中提出的組合結(jié)構(gòu)，在{3,4}-正則情形下獲得了更優(yōu)的下界。作為補(bǔ)充，我們還得到了新的上界，改進(jìn)了Hoffman的經(jīng)典譜界[Hof03, Hae21]。（這些上界通過(guò)解析方法1推導(dǎo)得出。）綜合上下界結(jié)果，我們幾乎完全解決了這些問(wèn)題2。

b) MAX-k-CUT的近似NP難性。在第3節(jié)中，我們針對(duì)k∈{3,4}的情形，給出了基于小工具的歸約（源自標(biāo)準(zhǔn)的H?stad型PCP [H?s01]），用于證明MAX-k-CUT的近似NP難性。對(duì)于MAX-4-CUT，我們將當(dāng)前最優(yōu)的不可近似性結(jié)果從0.9883 [AOTW14]改進(jìn)至0.987；對(duì)于MAX-3-CUT，我們將當(dāng)前最優(yōu)的基于小工具的不可近似性結(jié)果從0.9853 [KKLP96]改進(jìn)至0.9649。我們的MAX-3-CUT結(jié)果介于兩項(xiàng)使用定制化PCP的工作之間：[GS09]的0.9696與[AOTW14]的0.9411。

c) 度量旅行商問(wèn)題（TSP）的近似NP難性。在第4節(jié)中，我們給出了一個(gè)新的基于小工具的歸約（源自標(biāo)準(zhǔn)H?stad型PCP [H?s01]），用于證明度量TSP的近似NP難性。我們將當(dāng)前最優(yōu)結(jié)果117/116 [CC20]改進(jìn)至111/110。這一改進(jìn)推進(jìn)了該問(wèn)題硬度結(jié)果的長(zhǎng)期研究脈絡(luò)：[PY93, 1+δ]（未給出δ的顯式值）、[Eng99, 5381/5380]、[BHK+00, 3183/3182]、[PV06, 220/219]、[Lam14, 185/184]、[KLS15, 123/122]、[CC20, 117/116]。附帶說(shuō)明，我們基于AI的探索仍在進(jìn)行中，該界有望進(jìn)一步改進(jìn)。

值得注意的是，我們的結(jié)果均依賴于單一的（AI衍生）技術(shù)——AlphaEvolve [NVE+25, RPBN+24]，用于發(fā)現(xiàn)并驗(yàn)證優(yōu)于先前構(gòu)造的有限組合結(jié)構(gòu)。在高層次上，AlphaEvolve利用大語(yǔ)言模型（LLM）迭代演化生成組合結(jié)構(gòu)的代碼片段（我們有時(shí)稱之為“構(gòu)造”），并依據(jù)某種標(biāo)準(zhǔn)對(duì)這些結(jié)構(gòu)進(jìn)行質(zhì)量評(píng)估。盡管我們通過(guò)AlphaEvolve生成的結(jié)構(gòu)均為有限構(gòu)造，但借助適當(dāng)?shù)摹疤嵘保╨ifting）[KY24, TSSW00, CC20]論證，我們的主要結(jié)果（定理2.1、3.1與4.1）均蘊(yùn)含了對(duì)問(wèn)題規(guī)模n的全稱量詞?n。至少，我們的工作表明，我們應(yīng)當(dāng)常規(guī)性地將基于小工具的證明送入“AI優(yōu)化”階段。我們按人類參與程度（為使問(wèn)題適配AlphaEvolve所需）遞增的順序呈現(xiàn)這些結(jié)果。

在操作層面，該系統(tǒng)包含三個(gè)組成部分：a) 用于構(gòu)造組合結(jié)構(gòu)的代碼片段（C）；b) 用于驗(yàn)證并評(píng)分所生成結(jié)構(gòu)的評(píng)估函數(shù)（稱為驗(yàn)證器）；c) 基于先前C的集合與構(gòu)造歷史，建議新代碼片段Cnew的大語(yǔ)言模型。通過(guò)對(duì)LLM進(jìn)行提示，目標(biāo)是引導(dǎo)Cnew生成更優(yōu)的結(jié)構(gòu)。（附錄A提供了AlphaEvolve的更詳細(xì)概述。）

AlphaEvolve的有效性在根本上取決于驗(yàn)證步驟，后者進(jìn)而決定了搜索空間的形態(tài)。由于我們?cè)邶嫶蟮乃阉骺臻g中尋求極值結(jié)構(gòu)，對(duì)構(gòu)造進(jìn)行快速驗(yàn)證（包括評(píng)分）有助于AlphaEvolve嘗試大量組合結(jié)構(gòu)，并從中學(xué)習(xí)模式以剪枝搜索空間。我們最終為各問(wèn)題找到的結(jié)構(gòu)規(guī)模，與驗(yàn)證速度直接相關(guān)。

在AlphaEvolve中加速驗(yàn)證：這些問(wèn)題所尋求的組合結(jié)構(gòu)基于無(wú)向圖。盡管對(duì)TSP下界及稀疏隨機(jī)圖上界驗(yàn)證的暴力驗(yàn)證速度尚可接受，但對(duì)MAX-k-CUT而言，驗(yàn)證則顯著更具挑戰(zhàn)性。下文將對(duì)此進(jìn)行更詳細(xì)討論。

對(duì)于TSP，所發(fā)現(xiàn)的某個(gè)小工具包含20條邊（分布在12個(gè)頂點(diǎn)上）以及大量約束條件（約11!條）以完成成功驗(yàn)證。因此，我們需要精心編寫一個(gè)高速驗(yàn)證器，使其運(yùn)行時(shí)間控制在約一秒之內(nèi)。

2 隨機(jī)圖上的認(rèn)證問(wèn)題難度

我們?cè)诟戒汢.2中證明了該結(jié)果。為便于參考，我們整理了與先前結(jié)果的對(duì)比（見(jiàn)表1）。值得注意的是，我們獲得了與匹配的上下界，其絕對(duì)誤差僅0.005，因此定理2.1和2.2在這些情形下近乎最優(yōu)。特別地，這激發(fā)了一個(gè)令人振奮的可能性：通過(guò)研究定理2.1和2.2的證明，或許能夠獲得關(guān)于的完整刻畫(huà)。

關(guān)于使用AlphaEvolve尋找近乎最優(yōu)下界的評(píng)述。本節(jié)以定理2.1的方法論及結(jié)果作為結(jié)語(yǔ)。文獻(xiàn)[KY24]中針對(duì)d∈{3,4}給出的構(gòu)造是頂點(diǎn)數(shù)不超過(guò)12的圖，這些構(gòu)造通過(guò)計(jì)算機(jī)輔助實(shí)驗(yàn)生成。我們通過(guò)隨機(jī)采樣大量正則圖成功復(fù)現(xiàn)了他們的結(jié)果，盡管在構(gòu)造中對(duì)自環(huán)數(shù)量存在事后認(rèn)知。

改進(jìn)它們的下界需要在更多頂點(diǎn)上進(jìn)行構(gòu)造，因?yàn)?MC(G) 或 IS(G) 的粒度受限于 G 的大小。在我們目標(biāo)規(guī)模下，隨機(jī)采樣構(gòu)造的方法行不通，原因有二：（1）d-正則 n 頂點(diǎn)圖的空間呈組合爆炸式增長(zhǎng)，意味著隨機(jī)采樣無(wú)法找到有趣的"極值"圖；（2）計(jì)算 MC(G) 或 IS(G) 的復(fù)雜度關(guān)于 n 是指數(shù)級(jí)的，因此甚至很難為某個(gè)構(gòu)造計(jì)算這些邊界。

3 基于 Gadget 的 MAX-k-CUT 近似 NP-難性

近似算法領(lǐng)域 [WS11] 關(guān)注為計(jì)算困難的組合優(yōu)化問(wèn)題尋找近似最優(yōu)解。在近似難性 [AB09] 中，主要目標(biāo)是理解這種近似何時(shí)在計(jì)算上是困難的。我們?cè)谘芯砍浞值?strong>約束滿足問(wèn)題（CSPs）框架內(nèi)開(kāi)展工作。

在 Max-CSP 設(shè)置中，輸入是特定 CSP 實(shí)例 I 的描述，目標(biāo)是計(jì)算可以滿足的約束的最大數(shù)量。換句話說(shuō)，我們?cè)噲D近似計(jì)算函數(shù) 。通過(guò)引入 (c, s)-近似的概念，將近似問(wèn)題轉(zhuǎn)化為判定問(wèn)題是很有用的，如下所示。

與先前不可近似性結(jié)果的比較。據(jù)我們所知，當(dāng)前MAX-4-CUT的最佳困難性因子是85/86 + ε [AOTW14, 定理1.2]，我們通過(guò)定理3.2將其改進(jìn)到0.987。[AOTW14]中的困難性是通過(guò)從MAX-3-CUT到MAX-k-CUT（對(duì)所有k > 3）的歸約獲得的。至于MAX-3-CUT，我們將定理3.1中的結(jié)果與三項(xiàng)工作[KKLP96, GS09, AOTW14]進(jìn)行比較，這些工作為MAX-3-CUT獲得了逐步更強(qiáng)的NP困難性結(jié)果。我們?cè)诙ɡ?.1中的55/57 + ε不可近似性比率擊敗了[KKLP96]的67/68 + ε和[GS09]的32/33 + ε。我們的結(jié)果不足以擊敗Austrin、O'Donnell、Tan和Wright [AOTW14]使用從Label Cover的定制歸約獲得的16/17 + ε的最新技術(shù)。相比之下，我們的結(jié)果不需要任何新的PCP機(jī)制，僅利用H?stad的經(jīng)典PCP [H?s01]。我們不了解限制基于gadget的方法擊敗[AOTW14]不可近似比率的根本性障礙，可以想象，從不同的源問(wèn)題到3LIN(3)的基于gadget的歸約可以實(shí)現(xiàn)這一點(diǎn)。

3.1 為可靠性和完備性保證開(kāi)發(fā)搜索框架

為了將AlphaEvolve應(yīng)用于這個(gè)問(wèn)題，我們開(kāi)發(fā)了一個(gè)基于gadget歸約論證的模板，并分離了該論證中對(duì)gadget所需的性質(zhì)（詳見(jiàn)定義C.1和定理C.2）。我們通過(guò)候選gadget的最終性能來(lái)評(píng)分，即通過(guò)將定理C.2應(yīng)用于候選gadget所隱含的不可近似比率。

為MAX-3-CUT找到的所有g(shù)adget中，每條邊有0到3個(gè)副本。這是意料之中的，因?yàn)樵S多先前結(jié)果中找到的最優(yōu)gadget（例如 [TSSW00, HHM?17]）都包含小的整數(shù)權(quán)重。因此，我們得到了一個(gè)簡(jiǎn)潔的不可近似比 55/57。

尋找MAX-4-CUT的gadget。 我們尋找MAX-4-CUT gadget的過(guò)程與之前的主要區(qū)別在于，我們必須在變量更多的gadget中進(jìn)行搜索（多達(dá)19個(gè)變量），因此我們需要一個(gè)性能極高的驗(yàn)證器實(shí)現(xiàn)（同樣，我們將在第3.2節(jié)詳細(xì)闡述）。即使有了這個(gè)優(yōu)化后的驗(yàn)證器，評(píng)估速度仍然相當(dāng)慢，評(píng)估一個(gè)19變量的gadget大約需要一秒鐘。因此，AlphaEvolve花了更長(zhǎng)的時(shí)間才找到一個(gè)搜索算法，該算法在給定這個(gè)優(yōu)化驗(yàn)證器的情況下，能夠找到任何非平凡的gadget。AlphaEvolve最終產(chǎn)生的搜索算法具有一個(gè)獨(dú)特的特性：它在帶權(quán)gadget中進(jìn)行搜索，權(quán)重為實(shí)數(shù)值，經(jīng)過(guò)適當(dāng)?shù)目s放和舍入后，得到的gadget權(quán)重在1到1429之間變化很大。

3.2 通過(guò)AlphaEvolve實(shí)現(xiàn)更快的驗(yàn)證以探索更大的Gadget

尋找大型gadget的主要挑戰(zhàn)在于，對(duì)gadget進(jìn)行評(píng)分的成本隨變量數(shù)量呈指數(shù)級(jí)增長(zhǎng)；計(jì)算定義C.1中描述的完備性和可靠性參數(shù)本質(zhì)上相當(dāng)于求解一個(gè)MAX-k-CUT實(shí)例，這需要指數(shù)時(shí)間。即使對(duì)于，當(dāng)使用暴力MAX-3-CUT驗(yàn)證器搜索規(guī)模僅為11的gadget時(shí)，AlphaEvolve的速度也會(huì)顯著下降。

這個(gè)問(wèn)題沒(méi)有現(xiàn)成的解決方案，即不存在已有的快速驗(yàn)證器；現(xiàn)有的SMT/MIP求解器 [ES03, MML14] 也不太可能被改造用于求解MAX-k-CUT。為了解決這個(gè)問(wèn)題，我們使用AlphaEvolve本身來(lái)加速一個(gè)樸素的暴力MAX-k-CUT實(shí)現(xiàn)，通過(guò)運(yùn)行時(shí)間和正確性來(lái)對(duì)候選實(shí)現(xiàn)進(jìn)行評(píng)分。為了計(jì)算運(yùn)行時(shí)間，我們創(chuàng)建了一個(gè)綜合數(shù)據(jù)集，包含來(lái)自20個(gè)隨機(jī)模型的各種MAX-k-CUT實(shí)例，這些模型具有不同程度的植入結(jié)構(gòu)。然后，我們要求AlphaEvolve最大化變量數(shù) m，使得驗(yàn)證器在我們的數(shù)據(jù)集上求解規(guī)模為 m 的實(shí)例時(shí)，平均所需時(shí)間不超過(guò)一秒。

最大的挑戰(zhàn)是確保AlphaEvolve不會(huì)作弊，找到一個(gè)快得多但不正確的驗(yàn)證器。如前所述，我們通過(guò)以下方式實(shí)現(xiàn)正確性：(1) 檢查驗(yàn)證器在綜合數(shù)據(jù)集上的正確性，(2) 使用一個(gè)獨(dú)立的評(píng)判LLM來(lái)認(rèn)證候選驗(yàn)證器的正確性。這些技術(shù)單獨(dú)使用時(shí)都過(guò)于寬松，無(wú)法避免不正確的驗(yàn)證器，但通過(guò)人工檢查我們發(fā)現(xiàn)，將它們結(jié)合起來(lái)就足夠了。

我們注意到，一旦 m 足夠大，就無(wú)法使用暴力實(shí)現(xiàn)（保證正確）為我們的數(shù)據(jù)集標(biāo)注"ground truth"分?jǐn)?shù)。相反，我們歸納地依賴AlphaEvolve之前產(chǎn)生的驗(yàn)證器的正確性（這些驗(yàn)證器已經(jīng)通過(guò)了上述正確性檢查），它們足夠快，可以為較大的 m 提供標(biāo)簽。

3.3 與其他計(jì)算技術(shù)的比較

我們現(xiàn)在調(diào)研一些其他用于尋找gadget的計(jì)算技術(shù)，并討論為什么它們?cè)谖覀兲囟▎?wèn)題的規(guī)模上似乎是不可行的，即使是對(duì)于更簡(jiǎn)單的MAX-3-CUT設(shè)置。

最直接的比較是TSSW框架 [TSSW00]，它將尋找最優(yōu)gadget的任務(wù)轉(zhuǎn)化為一個(gè)線性規(guī)劃（LP）。這樣做主要困難在于計(jì)算gadget完備性時(shí)存在存在量詞。為了消除這些量詞，[TSSW00] 對(duì)gadget中的輔助變量進(jìn)行規(guī)范化。結(jié)果，編碼最優(yōu)gadget的LP規(guī)模在源謂詞的滿足賦值數(shù)量上是雙指數(shù)級(jí)的；對(duì)于從3LIN(3)到MAX-3-CUT的歸約，這個(gè)數(shù)字是，這在計(jì)算上是不可行的。有時(shí)（正如我們MAX-3-CUT的 gadget的情況），可以論證并非所有輔助變量都是必需的，從而得到一個(gè)更易處理的LP，但不清楚這在非常特殊的情況之外是否可行。

如果希望將gadget中的變量數(shù)固定為小于336的某個(gè)特定常數(shù)（如我們gadget的14個(gè)變量），可以通過(guò)使用整數(shù)變量編碼存在性約束，將線性規(guī)劃（LP）改為混合整數(shù)規(guī)劃（MIP）。例如，即使除一個(gè)存在性約束外其余全部消除，求解該MIP仍耗時(shí)10小時(shí)。（我們使用SCIP求解器 [BBB+24a, BBB+24b] 對(duì)問(wèn)題進(jìn)行直接編碼。）因此，MIP方法在使用最先進(jìn)（SOTA）求解器的情況下似乎也并不可行。

4 度量TSP近似計(jì)算的NP難性

這種MWST形式對(duì)難歸約特別有利。通過(guò)將關(guān)注點(diǎn)從尋找簡(jiǎn)單回路轉(zhuǎn)移到尋找最小成本的連通歐拉子圖，可以避免顯式構(gòu)造度量閉包的繁瑣任務(wù)。這使得歸約能夠在稀疏圖上局部定義權(quán)重——通常給邊分配小權(quán)重，給非邊分配大懲罰——同時(shí)確保原始困難實(shí)例的結(jié)構(gòu)性質(zhì)得以保持。

我們使用AlphaEvolve尋找一個(gè)gadget（稱為方程gadget）來(lái)改進(jìn)從Hybrid-3LIN(2)到MWST的歸約，同時(shí)保持其余論證不變。這立即將難近似因子從117/116改進(jìn)到了111/110。

使用AlphaEvolve，我們發(fā)現(xiàn)了一個(gè)新的方程gadget（圖4），其性能優(yōu)于[CC20]中出現(xiàn)的（圖8a）?。為了量化這一改進(jìn)，我們現(xiàn)在更具體地描述方程gadget：每個(gè)3LIN(2)方程?3?（形式為x⊕y⊕z=1）被分配一個(gè)方程gadget，其中圖4中的綠色頂點(diǎn){1,2,3}（也稱為接觸頂點(diǎn)）對(duì)應(yīng)變量{x,y,z}。紅色頂點(diǎn){4}被稱為中心頂點(diǎn)，并在實(shí)例中所有3LIN(2)方程的方程gadget的所有出現(xiàn)中共享。方程gadget中的其余頂點(diǎn)（在圖2中以藍(lán)色顯示）用于確保由滿足的3LIN(2)方程和不滿足的方程產(chǎn)生的生成環(huán)游的權(quán)重之間存在差距。黑色邊（稱為“非強(qiáng)制邊”）在任何環(huán)游中都是可選的，而任何環(huán)游都必須至少經(jīng)過(guò)每條紅色邊（稱為“強(qiáng)制邊”）一次。我們注意到，標(biāo)準(zhǔn)技巧（例如，[KLS15]）可用于實(shí)現(xiàn)強(qiáng)制某些邊在MWST中被選取的約束。綠色虛線邊稱為特殊邊，僅用于分析目的，在實(shí)際的MWST實(shí)例中不會(huì)出現(xiàn)。

如前所述，若方程gadget對(duì)生成環(huán)游的貢獻(xiàn)在子句滿足/不滿足時(shí)分別較小/較大，則該方程gadget表現(xiàn)良好。在下文中，我們將這一要求提煉為關(guān)于該gadget的自包含陳述。給定一個(gè)方程gadget，我們考慮其中覆蓋每個(gè)頂點(diǎn)的不相交環(huán)游集合。此類集合與(x,y,z)的特定賦值相關(guān)聯(lián)，其中當(dāng)且僅當(dāng)變量對(duì)應(yīng)的接觸頂點(diǎn)與中心頂點(diǎn)4出現(xiàn)在同一環(huán)游中時(shí)，該變量被賦值為True。此外，除包含中心頂點(diǎn)的環(huán)游外，每個(gè)環(huán)游都會(huì)受到權(quán)重懲罰1。對(duì)于3LIN(2)方程的賦值(x,y,z)，我們將關(guān)注與(x,y,z)相關(guān)的任何此類集合的可能最小總權(quán)重（包括任何權(quán)重懲罰）。我們注意到上述描述是簡(jiǎn)化的，因?yàn)樗纯紤]與約簡(jiǎn)其余部分以不希望的方式交互的“不誠(chéng)實(shí)”環(huán)游集合。為了處理這些情況，我們?cè)谛问交C明中采用略微不同的形式化方法，將討論推遲到附錄D.2。

我們對(duì)方程gadget的改進(jìn)：AlphaEvolve找到的改進(jìn)型方程gadget（圖4）允許與3LIN(2)方程的滿足賦值相關(guān)聯(lián)的集合總權(quán)重為10，與不滿足賦值相關(guān)聯(lián)的至少為11，而[CC20]中的gadget分別為13和14。這立即改進(jìn)了約簡(jiǎn)的性能，使MWST（以及等價(jià)的度量TSP）的不可近似比從117/116提高到111/110。我們新gadget的描述、完整約簡(jiǎn)以及作為方程gadget函數(shù)的最終不可近似比的證明在附錄D中提供。

雖然我們?cè)趫D4中展示了對(duì)應(yīng)于謂詞x⊕y⊕z=1的方程gadget，但我們可以使用對(duì)應(yīng)于x⊕y⊕z=0的gadget（與[CC20]中的設(shè)置相同）獲得相同的近似比。然而，該gadget更為復(fù)雜。我們將它的描述以及與[CC20]的并排比較推遲到附錄D.3。

核心思想及AlphaEvolve的重要性：在本文討論的問(wèn)題中，TSP需要最多的人工參與，主要因?yàn)椴淮嬖诂F(xiàn)有的gadget約簡(jiǎn)搜索框架（類似于[TSSW00]用于MAX-k-CUT）。特別是，[CC20]中的完整約簡(jiǎn)包含方程gadget之外的腳手架，且約簡(jiǎn)的所有組件作為單個(gè)對(duì)象一起分析。在先前工作[CC20,KLS15]的證明結(jié)構(gòu)中，似乎不清楚如何抽象出一組可驗(yàn)證的約束，使得AlphaEvolve可以單獨(dú)用于搜索更好的方程gadget。在本工作中，我們將可靠性和完備性證明模塊化，使其依賴于明確定義的可靠性和完備性參數(shù)，這些參數(shù)被定義為方程gadget本身的優(yōu)化問(wèn)題（定義D.4）。這種模塊化對(duì)未來(lái)工作可能具有獨(dú)立的研究?jī)r(jià)值。我們使用AlphaEvolve搜索方程gadget，以最大化從這些可靠性和完備性參數(shù)獲得的最終不可近似比。

方程gadget搜索的優(yōu)化問(wèn)題可表述為混合整數(shù)規(guī)劃（MIP）。由于其簡(jiǎn)單性，可以想見(jiàn)：若預(yù)先已知輔助頂點(diǎn)數(shù)量，圖4中的gadget可通過(guò)直接求解該MIP得到。然而，由于對(duì)應(yīng)x⊕y⊕z=0的方程gadget（圖8b）涉及大量約束（約11!條），使用傳統(tǒng)SMT/MIP求解器將面臨與MAX-k-CUT問(wèn)題相同（第3.3節(jié)所述）的計(jì)算瓶頸。

5 關(guān)于AI輔助數(shù)學(xué)與復(fù)雜性理論的討論

在研究AI輔助數(shù)學(xué)發(fā)現(xiàn)的作用時(shí)，我們至少需要考慮以下幾種情形：

1. 調(diào)用語(yǔ)言模型來(lái)總結(jié)某一領(lǐng)域的既有成果，規(guī)劃通往新定理的研究路徑，或直接生成（部分乃至完整）證明；
2. 使用AlphaEvolve等由AI衍生的工具來(lái)生成更優(yōu)的證明構(gòu)件（如gadget、圖結(jié)構(gòu)）；
3. 使用獨(dú)立于AI的定制代碼來(lái)發(fā)現(xiàn)更優(yōu)的證明構(gòu)件；
4. 通過(guò)手工方式發(fā)現(xiàn)相同或更優(yōu)的證明構(gòu)件；
5. 上述（1）–（4）情形的組合。

文獻(xiàn)綜述：大語(yǔ)言模型（LLM）能夠有效生成領(lǐng)域內(nèi)既有文獻(xiàn)的綜述，這一觀點(diǎn)已被討論了一段時(shí)間 [WLNR23, WZLJ23, HLL+24, GUK+24]，我們的實(shí)際體驗(yàn)也通過(guò)多個(gè)提示驗(yàn)證了這一點(diǎn)。所得結(jié)果（除偶爾出現(xiàn)幻覺(jué)外）為更深入的探索與理解提供了良好起點(diǎn)。有趣的是，在諸多案例中，我們能夠快速生成一個(gè)陌生領(lǐng)域的研究現(xiàn)狀概覽；我們相信，這一能力將日益被跨領(lǐng)域工作的科學(xué)家所采用，例如使代數(shù)學(xué)家能夠迅速掌握拉姆齊理論。我們預(yù)計(jì)，隨著時(shí)間推移，這將促進(jìn)學(xué)科間更流暢的知識(shí)交融。然而，我們尚未能通過(guò)提示使LLM生成可用于獲得新結(jié)果（如本文所報(bào)告結(jié)果）的可行研究計(jì)劃，這正是更深層努力的焦點(diǎn)，例如Google的Co-Scientist計(jì)劃 [GWD+25]。

直接提示：已有若干研究嘗試通過(guò)直接提示LLM來(lái)為開(kāi)放性數(shù)學(xué)命題生成證明 [Raa25, Bub25, OD25, DdMN25, JR25, BCE+25]，成效不一。在某些情況下，LLM確實(shí)能夠生成先前未被證明命題的完整且正確的證明 [Bub25, BCE+25]（盡管堅(jiān)持不懈的人類研究者或許也能推導(dǎo)出相同結(jié)果）；但在更多情況下 [Raa25, OD25, DdMN25, JR25]，LLM僅能生成證明草圖，最終仍需人類補(bǔ)全。截至本文撰寫時(shí)，該方向一項(xiàng)重要工作是 [BCE+25]。該報(bào)告記錄了GPT-5在加速數(shù)學(xué)與理論計(jì)算機(jī)科學(xué)研究方面的能力，展示了“腳手架”技術(shù)——即通過(guò)更簡(jiǎn)單、相關(guān)的熱身問(wèn)題對(duì)模型進(jìn)行預(yù)訓(xùn)練——如何使其推導(dǎo)出在線算法的改進(jìn)界，并形式化證明了圖論中先前開(kāi)放的猜想。作者強(qiáng)調(diào)，該模型能夠超越單純的信息檢索，成功構(gòu)建出曾令人類專家束手無(wú)策的新穎反例與證明策略，例如為凸體追蹤問(wèn)題中的“Follow-the-Leader”算法生成復(fù)雜反例，以及提出解決Erd?s問(wèn)題[Blo]。

總體而言，當(dāng)前這些證明/草圖仍需人類驗(yàn)證其正確性。我們?cè)匀坏貒L試通過(guò)提示標(biāo)準(zhǔn)LLM直接生成本文中的組合結(jié)構(gòu)，但均告失敗?。盡管隨著LLM推理能力的提升 [LL25]，這一目標(biāo)未來(lái)或可實(shí)現(xiàn)，但正式比較已超出本文范圍。我們強(qiáng)調(diào)，我們的構(gòu)造始終附帶可通過(guò)標(biāo)準(zhǔn)計(jì)算方法形式驗(yàn)證的正確性證書(shū)；一旦驗(yàn)證代碼可靠，便無(wú)需進(jìn)一步的人工審查。

展示AlphaEvolve的廣度：近期論文 [GGSTW25] 全面展示了由LLM引導(dǎo)的進(jìn)化搜索（AlphaEvolve）如何在分析、組合與幾何領(lǐng)域中自主發(fā)現(xiàn)新穎數(shù)學(xué)構(gòu)造，其成果令人驚嘆——例如通過(guò)創(chuàng)造性地對(duì)驗(yàn)證用語(yǔ)言模型實(shí)施“提示注入”，找到了“四守衛(wèi)”邏輯謎題的反例。該方法顯著改進(jìn)了諸如掛谷針問(wèn)題與環(huán)加載問(wèn)題等長(zhǎng)期難題的界，且往往僅需極少問(wèn)題定制調(diào)優(yōu)，即可達(dá)到與人類設(shè)計(jì)基準(zhǔn)相當(dāng)甚至更優(yōu)的結(jié)果。

近似難度中的計(jì)算方法：在隨機(jī)圖的平均情況難度與MAX-k-CUT的NP難度近似問(wèn)題中，此前已使用過(guò)計(jì)算機(jī)輔助方法 [TSSW00, H?s01, KY24]。[KY24] 利用計(jì)算方法生成了具有較大割值（或獨(dú)立集）的d-正則拉馬努金圖（d ∈ {3, 4}）。盡管他們未明確說(shuō)明計(jì)算方法，但我們可通過(guò)隨機(jī)采樣d-正則圖并暴力測(cè)試其性質(zhì)來(lái)復(fù)現(xiàn)其結(jié)果?；诘?節(jié)所述原因，[KY24] 僅能對(duì)n ≤ 12證明其下界，而我們發(fā)現(xiàn)的圖可達(dá)n = 163。

對(duì)于第3節(jié)中的NP難度gadget歸約，可靠性和完備性約束均可通過(guò)斯科倫化轉(zhuǎn)化為線性規(guī)劃 [TSSW00]。然而，此類線性規(guī)劃的規(guī)模隨約束圖頂點(diǎn)數(shù)呈雙重指數(shù)增長(zhǎng)。因此，即便是MAX-3-CUT問(wèn)題，使用標(biāo)準(zhǔn)線性規(guī)劃求解器處理 [TSSW00] 中典型變量數(shù)（≈336）的線性規(guī)劃也已不可行。也可直接使用SMT/MIP求解器處理非凸規(guī)劃，但當(dāng)變量數(shù)n ≥ 14時(shí)，約束數(shù)量呈指數(shù)級(jí)增長(zhǎng)，這些求解器同樣難以擴(kuò)展（詳見(jiàn)第3.3節(jié)討論）。在TSP近似難度問(wèn)題中，可靠性和完備性約束亦可表述為MIP約束；即便方程gadget的頂點(diǎn)數(shù)適中（如圖8b中的12個(gè)），約束數(shù)量也會(huì)變得極其龐大（約11! ≈ 3 × 10?），超出標(biāo)準(zhǔn)MIP求解器的處理能力。

手工設(shè)計(jì)gadget：理論上，人類專家或高度定制的計(jì)算驗(yàn)證器最終或許能發(fā)現(xiàn)這些解。然而，其發(fā)現(xiàn)很可能已超出簡(jiǎn)單“紙筆推導(dǎo)”方法的能力范圍，且標(biāo)準(zhǔn)SMT/MIP求解器亦未能生成它們。此外，人類通常憑借對(duì)構(gòu)造對(duì)象對(duì)稱性的洞察來(lái)直覺(jué)性地裁剪搜索空間；而在我們的TSP gadget中，不對(duì)稱性似乎是實(shí)現(xiàn)改進(jìn)的關(guān)鍵。

AI與大量人力結(jié)合：我們的工作與 [Tao25] 均屬于AI與顯著人力投入相結(jié)合的范例。特別是，[Tao25] 記錄了通過(guò)混合工作流快速解決Erd?s問(wèn)題 [Blo] 的過(guò)程：人類智慧引導(dǎo)多個(gè)AI系統(tǒng)——包括用于生成最優(yōu)構(gòu)造的AlphaEvolve，以及用于在Lean中進(jìn)行形式驗(yàn)證的自動(dòng)定理證明器Aristotle [ABB+25]。通過(guò)整合眾包數(shù)學(xué)洞見(jiàn)、AI驅(qū)動(dòng)的深度文獻(xiàn)檢索與計(jì)算發(fā)現(xiàn)，該協(xié)作在48小時(shí)內(nèi)成功生成了解答。在我們的案例中，為使問(wèn)題適用于AlphaEvolve，我們不得不（手工）重構(gòu)度量TSP的證明邏輯。

秉承圖靈模仿游戲 [Tur50] 的精神，對(duì)AI輔助數(shù)學(xué)發(fā)現(xiàn)穩(wěn)健性的一項(xiàng)有力檢驗(yàn)是持久性（durability）：即通過(guò)AI輔助獲得的新成果是否會(huì)被人類（可能借助計(jì)算機(jī)輔助）迅速超越。我們注意到，某些AI輔助數(shù)學(xué)的成果事實(shí)上已被人類在不使用AI的情況下快速?gòu)?fù)現(xiàn)或改進(jìn) [Ger25, BSZ25]；在某些情況下，相關(guān)結(jié)果甚至早已存在（有時(shí)甚至在問(wèn)題被明確提出之前 [Alo24, Rec25]），但在應(yīng)用AI方法時(shí)作者并不知曉 [AM25, BCE+25]。

結(jié)語(yǔ)：盡管我們?cè)诖说慕?jīng)驗(yàn)有限且遠(yuǎn)非定論，但我們認(rèn)為一些早期主題正在浮現(xiàn)。

首先，語(yǔ)言模型能夠生成研究計(jì)劃并總結(jié)領(lǐng)域現(xiàn)狀 [GWD+25]。盡管我們尚未能借此直接推導(dǎo)出新穎結(jié)果，但這一能力使非專業(yè)人士能夠快速學(xué)習(xí)新領(lǐng)域，我們預(yù)計(jì)這將促進(jìn)更廣泛的科學(xué)交叉融合。

其次，我們預(yù)計(jì)未來(lái)將出現(xiàn)越來(lái)越多“AI率先抵達(dá)”的證明，但往往缺乏“若無(wú)AI則無(wú)法完成”的明確證據(jù)。在所有這些案例中（且可論證地，在AI應(yīng)用于科學(xué)的廣泛場(chǎng)景中），驗(yàn)證環(huán)節(jié)將持續(xù)成為瓶頸。我們留待一個(gè)開(kāi)放問(wèn)題：直接提示LLM最終能否復(fù)現(xiàn)并超越我們的結(jié)果。

第三，我們的工作表明，基于gadget的歸約方法適合采用AlphaEvolve進(jìn)行超越傳統(tǒng)方法（如SMT/MIP求解器）的優(yōu)化。這反過(guò)來(lái)暗示，若要超越AlphaEvolve，通常需要采用非gadget方法，例如定制化的概率可檢驗(yàn)證明（PCP）[AOTW14]。

最后，值得反思我們方法的一些失敗案例。對(duì)于某些問(wèn)題，即便驗(yàn)證極為簡(jiǎn)單，AlphaEvolve仍無(wú)法奏效。一個(gè)例子是Hadamard-668猜想，該猜想斷言存在668×668階的Hadamard矩陣（更一般地，猜想對(duì)任意4的倍數(shù)n均存在n×n階Hadamard矩陣；668是目前尚未獲證的最小階數(shù)）。我們?cè)鴩L試用AlphaEvolve構(gòu)造該矩陣。盡管搜索空間龐大（達(dá)2???2種可能），但驗(yàn)證任一候選解的正確性僅需2、23、112次按位乘法。即便驗(yàn)證速度極快，AlphaEvolve仍未能找到H???×???的構(gòu)造；事實(shí)上，我們甚至未能讓AlphaEvolve復(fù)現(xiàn)H???×???的構(gòu)造——該階數(shù)曾是此前未知構(gòu)造的最小階數(shù)，直至[KTR05]給出解法；而428階的構(gòu)造方案其實(shí)早已公開(kāi)于互聯(lián)網(wǎng)。

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

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