近日，中國科學院金屬研究所研究員張志東確定了“背包問題”的計算復雜度下限，在該領(lǐng)域取得理論進展。
“背包問題”是計算機科學中經(jīng)典的NP完全問題（非確定性圖靈機多項式復雜度求解的決定問題）?！氨嘲鼏栴}”的目標是，在限制所有物體權(quán)重之和小于或等于最大權(quán)重的前提下，最大化所有物體的價值之和?！氨嘲鼏栴}”可用來進行組合數(shù)學、密碼學、商業(yè)等領(lǐng)域的計算，還可以應用在不同領(lǐng)域的決策，如尋找減少原材料使用、投資組合的選擇、密鑰產(chǎn)生等最優(yōu)化搜尋路徑。
“背包問題”與自旋玻璃模型的聯(lián)系是，“背包問題”的二元決定性變量對應于自旋向上和自旋向下兩種狀態(tài)?！氨嘲鼏栴}”的權(quán)重對應于自旋之間的相互作用?！氨嘲鼏栴}”的哈密頓量可以映射成具有偏置場的自旋玻璃模型的哈密頓。因此，通過求解自旋玻璃模型可以求解“背包問題”。在“背包問題”中最大化所有物體的價值之和等價于在自旋玻璃模型中最小化自由能。
該研究分析了NP完全問題中非平庸拓撲結(jié)構(gòu)的起源。研究從自旋玻璃三維伊辛模型出發(fā)，闡明三維晶格上自旋排列與統(tǒng)計物理中轉(zhuǎn)移矩陣的二維特征之間的矛盾導致非平庸拓撲結(jié)構(gòu)。研究確認，自旋玻璃三維伊辛模型存在絕對極小核心模型，為一層晶格自旋玻璃伊辛模型與其最近鄰層自旋的相互作用。它等于兩層晶格自旋玻璃三維伊辛模型減去一個自旋玻璃二維伊辛模型。研究發(fā)現(xiàn)，用蠻力搜索絕對極小核心模型決定其計算復雜度的下限。同時，研究發(fā)現(xiàn)自旋玻璃三維伊辛模型存在NP中間問題，給出體系的計算復雜度的相圖。絕對極小核心模型存在于NP完全問題和NP中間問題的邊界上。進一步，研究根據(jù)自旋玻璃三維伊辛模型和“背包問題”之間的映射，證明“背包問題”同樣存在絕對極小核心模型和NP中間問題，給出“背包問題”的計算復雜度相圖，并證明“背包問題”的計算復雜度的下限是亞指數(shù)、超多項式的。
該研究以物理思想為指導，分析體系的數(shù)學結(jié)構(gòu)，提出一個判據(jù)，確定了NP完全問題的計算復雜度的下限為（1+無限小）的N次方。同時，這一成果為NP完全問題的數(shù)值計算提供了指導性思維。
上述研究建立了“背包問題”與自旋玻璃三維伊辛模型的聯(lián)系，并根據(jù)兩個問題的關(guān)系確定了“背包問題”的計算復雜度的下限。同時，該工作得出的結(jié)論有望直接推廣應用，來解決計算機、物理、化學、生物、數(shù)學和材料科學領(lǐng)域相關(guān)的基礎科學問題。
相關(guān)研究成果發(fā)表在《AIMS數(shù)學》（AIMS Mathematics）上。
圖1.自旋玻璃三維伊辛模型最小核模型示意圖，其中紅色自旋指向隨機分布，并且藍色自旋存在阻錯。
圖2. 自旋玻璃三維伊辛模型體系計算度的相圖。其中NP中間問題(NPI)在NP完全問題與P問題之間，絕對最小核(AMC)模型在NP完全問題與NP中間問題的邊界上。
圖3. 背包問題計算度的相圖。其中NP中間問題(NPI)在NP完全問題與P問題之間，絕對最小核(AMC)模型在NP完全問題與NP中間問題的邊界上。
