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