據(jù)中國科學(xué)院金屬研究所消息，該所張志東研究員首次確定了“背包問題”的計(jì)算復(fù)雜度下限，在該領(lǐng)域取得重大理論進(jìn)展，相關(guān)成果近日發(fā)表于《AIMS數(shù)學(xué)》。

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

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

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

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

這項(xiàng)研究打破了傳統(tǒng)認(rèn)知，證明NP完全問題存在亞指數(shù)級算法，并首次精確確定了“背包問題”的計(jì)算速度極限。業(yè)內(nèi)專家稱，該研究的結(jié)論可以直接推廣應(yīng)用，解決計(jì)算機(jī)、物理、化學(xué)、生物、數(shù)學(xué)以及材料科學(xué)領(lǐng)域一系列相關(guān)基礎(chǔ)科學(xué)問題。

來源丨光明日報(bào)初審 | 陳嘉琦、李書豪復(fù)審 | 魏星華
終審 | 韓永林