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

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

據介紹，在10余年三維伊辛模型研究工作的基礎上，張志東建立起“背包問題”與自旋玻璃三維伊辛模型的聯(lián)系，根據兩個問題的關系確定“背包問題”的計算復雜度下限。

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

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

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

分享讓更多人看到