我科學家破解“揹包問題”複雜度之謎

日前從中國科學院金屬研究所獲悉，該所張志東研究員首次確定了“揹包問題”的計算複雜度下限，在該領域取得重大理論進展，相關成果近日發表於《AIMS數學》。

“揹包問題”是計算機科學中經典的NP完全問題(非確定性圖靈機多項式複雜度求解的決定問題)，可應用在不同領域的決策，如尋找減少原材料使用、投資組合的選擇、密鑰產生等最優化搜尋路徑。想象一個場景：面對薯片、巧克力、礦泉水等十幾種零食，如何在書包限重5斤的前提下選出“幸福值”最高的組合？這個生活化問題正是“揹包問題”的簡化版。當物品數量超過一定規模後，即使用最先進的計算機也需耗費天文數字時間求解，而計算複雜度下限就是解決問題所需的最少時間。

據介紹，在10餘年三維伊辛模型研究工作的基礎上，張志東建立起“揹包問題”與自旋玻璃三維伊辛模型的聯繫，根據兩個問題的關係確定“揹包問題”的計算複雜度下限。

自旋玻璃是一種特殊磁性材料，其中的微觀磁針（自旋）像一羣鬧彆扭的小朋友，有的執拗向上，有的堅持向下。張志東把“揹包問題”中每個物品的“拿或不拿”對應為磁針的“向上或向下”，而尋找最優解相當於在這羣互相拉扯的“磁針小朋友”中找到最省力的排列方式（最低能量狀態）。

研究發現微觀磁針排列的複雜糾纏結構就像被貓抓亂的毛線團，是導致計算困難的核心。張志東找出了這種糾纏結構的最小單位，即“絕對極小核心模型”，它就像毛線團裏最關鍵的那個結，恰好卡在NP完全問題與NP中間問題的分界線上。據此，張志東進一步構建計算複雜度相圖，首次明確NP完全問題與稍簡單的NP中間問題的分界線，從而確定複雜度下限，證明最優算法的時間複雜度至少為（1+無限小）的N次方，顯著優於現有算法。

這項研究打破了傳統認知，證明NP完全問題存在亞指數級算法，並首次精確確定了“揹包問題”的計算速度極限。業內專家稱，該研究的結論可以直接推廣應用，解決計算機、物理、化學、生物、數學以及材料科學領域一系列相關基礎科學問題。

《光明日報》（2025年05月30日 08版）