中評社北京5月30日電／據光明日報報導，記者日前從中國科學院金屬研究所獲悉，該所張志東研究員首次確定了“背包問題”的計算複雜度下限，在該領域取得重大理論進展，相關成果近日發表於《AIMS數學》。
“背包問題”是計算機科學中經典的NP完全問題（非確定性圖靈機多項式複雜度求解的決定問題），可應用在不同領域的決策，如尋找減少原材料使用、投資組合的選擇、密鑰產生等最優化搜尋路徑。想象一個場景：面對薯片、巧克力、礦泉水等十幾種零食，如何在書包限重5斤的前提下選出“幸福值”最高的組合？這個生活化問題正是“背包問題”的簡化版。當物品數量超過一定規模後，即使用最先進的計算機也需耗費天文數字時間求解，而計算複雜度下限就是解決問題所需的最少時間。
據介紹，在10餘年三維伊辛模型研究工作的基礎上，張志東建立起“背包問題”與自旋玻璃三維伊辛模型的聯繫，根據兩個問題的關係確定“背包問題”的計算複雜度下限。
自旋玻璃是一種特殊磁性材料，其中的微觀磁針（自旋）像一群鬧別扭的小朋友，有的執拗向上，有的堅持向下。張志東把“背包問題”中每個物品的“拿或不拿”對應為磁針的“向上或向下”，而尋找最優解相當於在這群互相拉扯的“磁針小朋友”中找到最省力的排列方式（最低能量狀態）。
研究發現微觀磁針排列的複雜糾纏結構就像被貓抓亂的毛線團，是導致計算困難的核心。張志東找出了這種糾纏結構的最小單位，即“絕對極小核心模型”，它就像毛線團裡最關鍵的那個結，恰好卡在NP完全問題與NP中間問題的分界線上。據此，張志東進一步構建計算複雜度相圖，首次明確NP完全問題與稍簡單的NP中間問題的分界線，從而確定複雜度下限，證明最優算法的時間複雜度至少為（1＋無限小）的N次方，顯著優於現有算法。
這項研究打破了傳統認知，證明NP完全問題存在亞指數級算法，並首次精確確定了“背包問題”的計算速度極限。業內專家稱，該研究的結論可以直接推廣應用，解決計算機、物理、化學、生物、數學以及材料科學領域一系列相關基礎科學問題。 |
