我國科學家在NP完全問題計算復雜性的研究方面取得重要進展。中國科學院金屬研究所張志東研究員確定了背包問題的計算復雜度下限。論文發表在AIMS Mathematics 10 (2025) 11918-11938。
隨著計算機領域的技術進步，人工智能正在影響我們日常生活的方方面面。而人工智能的進步依賴于計算算法的速度。如何在最短時間內算出正確的解是計算機領域科學家最關心的問題。NP完全問題是計算機科學中非常重要的難題。在計算復雜性理論中，NP表示非確定性多項式時間，NP問題定義為在一個非確定性圖靈機上以多項式時間求解的決定性問題的集合。P問題是在確定性圖靈機上以多項式時間求解的問題的集合。在NP中，以多項式時間確認解的決定性問題的集合歸類為NP完全問題。在NP中所有其他問題都可以在多項式時間內約化為NP完全問題（以及其特例）。著名的NP完全問題有：布爾可滿足性問題、旅行推銷員問題、背包問題、哈密頓環問題、子集和問題、頂角覆蓋問題、子圖同構問題、獨立集合問題、圖著色問題、蛋白質折疊問題、自旋玻璃問題等。這一類非平凡難題的共同特征是具有隨機性的模型系統中存在非平庸拓撲結構、非平面性圖、非局域性或長程自旋糾纏。
針對N個具有固定權重和價值的二元變量的決定性問題，背包問題的目標是，在限制所有物體權重之和小于或者等于最大權重的前提下，最大化所有物體的價值之和。背包問題可以用來進行組合數學、密碼學、商業等領域的計算，還可以應用在不同領域的決策，如尋找減少原材料使用、投資組合的選擇、密鑰產生等最優化搜尋路徑。背包問題與自旋玻璃模型的聯系：背包問題的二元決定性變量對應于自旋向上和自旋向下兩種狀態。背包問題的權重對應于自旋之間的相互作用。背包問題的哈密頓量可以映射成具有偏置場的自旋玻璃模型的哈密頓。所以，可以通過求解自旋玻璃模型求解背包問題。在背包問題中最大化所有物體的價值之和等價于在自旋玻璃模型中最小化自由能。
張志東首先分析了NP完全問題中非平庸拓撲結構的起源。從自旋玻璃三維伊辛模型出發，詳細地闡明三維晶格上自旋排列與統計物理中轉移矩陣的二維特征之間的矛盾導致非平庸拓撲結構。確認自旋玻璃三維伊辛模型存在絕對極小核心(AMC)模型，為一層晶格自旋玻璃伊辛模型與其最近鄰層自旋的相互作用。它等于兩層晶格自旋玻璃三維伊辛模型減去一個自旋玻璃二維伊辛模型。用蠻力搜索絕對極小核心模型決定了其計算復雜度的下限。并且，確認自旋玻璃三維伊辛模型中存在NP中間問題，給出體系的計算復雜度的相圖。絕對極小核心模型存在于NP完全問題和NP中間問題的邊界上。進一步地，根據自旋玻璃三維伊辛模型和背包問題之間的映射，證明背包問題同樣存在絕對極小核心模型和NP中間問題，也給出背包問題的計算復雜度相圖。并且證明了背包問題的計算復雜度的下限是亞指數、超多項式的。
本項工作通過物理思想做指導，分析體系的數學結構，提出一個判據，確定了NP完全問題的計算復雜度的下限為(1+無限小)的N次方。本項工作為NP完全問題的數值計算提供了指導性思維，例如通過發展絕對極小核心模型的平行計算，將會極大地優化算法，從目前的1.3的N次方提升至(1+無限小)的N次方。在保持一定計算精度的條件下，用亞指數算法獲得復雜系統（如自旋玻璃三維伊辛模型、背包問題等）的精確結果。
本項工作建立了背包問題與自旋玻璃三維伊辛模型的聯系，根據兩個問題的關系確定了背包問題的計算復雜度的下限。背包問題可以被映射為許多其它的科學問題，所以本項工作的結論可以直接推廣應用，解決計算機、物理、化學、生物、數學以及材料科學領域一系列相關基礎科學問題。
論文鏈接
圖1.自旋玻璃三維伊辛模型最小核模型示意圖，其中紅色自旋指向隨機分布，并且藍色自旋存在阻錯。
圖2. 自旋玻璃三維伊辛模型體系計算度的相圖。其中NP中間問題(NPI)在NP完全問題與P問題之間，絕對最小核(AMC)模型在NP完全問題與NP中間問題的邊界上。
圖3. 背包問題計算度的相圖。其中NP中間問題(NPI)在NP完全問題與P問題之間，絕對最小核(AMC)模型在NP完全問題與NP中間問題的邊界上。
AI讀進展：中國科學家破解“背包難題”復雜度之謎：計算速度極限被發現
一、為什么“背包問題”讓科學家頭疼？
想象你是個準備春游的小學生，書包只能裝5斤重的東西。面前有10種零食：薯片（200g，開心值+5）、巧克力（150g，開心值+8）……如何搭配才能既不超過重量，又讓你玩得最開心？這就是“背包問題”的童年版。
成年人世界的升級版：
- 如果有100種零食，組合方式會超過宇宙中的原子總數（10^80）
- 傳統算法需要檢查所有可能組合，耗時指數級增長（比如2^N次操作，N是物品數量）
- 這就是NP完全問題的恐怖之處：問題規模稍大，計算機就算到天荒地老
二、什么是“計算復雜度下限”？
可以理解為解決問題所需的最少時間。比如：
- 整理書包：最低需要1分鐘（下限），實際可能需要更久
- 背包問題：科學家發現，任何算法至少需要(1+ε)^N 的時間（ε≈0）
- 過去認為下限是2^N（指數爆炸）
- 新發現證明存在更優算法（亞指數級），但永遠快不過(1+ε)^N
類比：
假設你要試遍所有密碼鎖組合：
- 傳統觀點：必須試完10000種組合（10^4）
- 新發現：存在一種方法，只需試100.0001種（接近線性增長）
三、物理學家如何用“自旋玻璃”破解數學難題？
自旋玻璃是一種特殊磁性材料，微觀磁針（自旋）像一群鬧別扭的小朋友：
- 有的磁針想朝上，有的想朝下
- 彼此之間還會互相拉扯（相互作用）
- 整體處于混亂但穩定的狀態
科學家的大腦洞：
1.?物品選擇 → 磁針方向
背包里“選或不選”一個物品，對應磁針“朝上或朝下”
2.?總價值最大化 → 能量最小化
找到價值最高的組合，等價于讓自旋玻璃系統能量最低
3.?三維晶格拓撲 → 計算復雜度來源
發現自旋排列的復雜糾纏結構（類似毛線團打結），是導致計算困難的核心
四、這項研究到底多厲害？
理論層面
- 打破傳統認知：證明NP完全問題存在亞指數級算法（介于多項式與指數之間）
- 繪制計算相圖：首次明確NP完全問題與稍簡單的NP中間問題（如質因數分解）的邊界
應用層面
- 密碼學：當前加密貨幣依賴“背包問題很難解”，新算法可能威脅/加固加密體系
- 物流優化：港口集裝箱裝載效率提升10%~30%
- AI訓練：加速神經網絡參數搜索，降低算力消耗
五、普通人能感受到什么變化？
- 快遞更快：貨車裝載優化后，你的網購包裹可能早1天到貨
- 投資更賺：基金公司用新算法優化投資組合，年化收益提升2%~5%
- 天氣預報更準：復雜氣候模型計算提速，暴雨預警提前3小時
六、未解之謎：P vs NP 問題
這是計算機領域的終極問題之一，懸賞100萬美元（克雷數學研究所）：
- P問題：容易驗證答案，也容易求解（比如排序數字）
- NP問題>：容易驗證答案，但求解困難（比如背包問題）
- 世紀之問：P=NP嗎？如果成立，所有NP問題都能快速求解，密碼學將崩潰，AI會飛躍
張志東研究員的研究暗示：
P≠NP。即使P≠NP，NP完全問題也可能存在比傳統指數算法更優的解法，為破解P/NP之謎提供新路徑。
趣味小測試
假設你的背包能裝15kg，有以下物品：
-?筆記本電腦（2kg，價值8）
-?相機（3kg，價值10）
-?金條（10kg，價值30）
-?充電寶（1kg，價值3）
-?水壺（4kg，價值5）
你能找到總價值最大的組合嗎？
這項研究告訴我們：最優化選擇不僅需要智慧，還需要突破數學與物理的邊界。下次整理行李時，也許可以自豪地說：“我正在解決一個NP完全問題！” ???
聲明：“AI讀進展”內容由人工智能技術生成，其內容旨在輔助讀者初步了解相關領域研究動態，不代表中國科學院金屬研究所正式學術觀點或完整研究成果，不作為學術論證依據。
文檔附件
