近日，中國科學院金屬研究所研究員張志東確定了“背包問題”的計算復雜度下限，在該領域取得理論進展。
“背包問題”是計算機科學中經(jīng)典的NP完全問題（非確定性圖靈機多項式復雜度求解的決定問題）。“背包問題”的目標是，在限制所有物體權重之和小于或等于最大權重的前提下，最大化所有物體的價值之和。“背包問題”可用來進行組合數(shù)學、密碼學、商業(yè)等領域的計算，還可以應用在不同領域的決策，如尋找減少原材料使用、投資組合的選擇、密鑰產(chǎn)生等最優(yōu)化搜尋路徑。
“背包問題”與自旋玻璃模型的聯(lián)系是，“背包問題”的二元決定性變量對應于自旋向上和自旋向下兩種狀態(tài)。“背包問題”的權重對應于自旋之間的相互作用。“背包問題”的哈密頓量可以映射成具有偏置場的自旋玻璃模型的哈密頓。因此，通過求解自旋玻璃模型可以求解“背包問題”。在“背包問題”中最大化所有物體的價值之和等價于在自旋玻璃模型中最小化自由能。
該研究分析了NP完全問題中非平庸拓撲結構的起源。研究從自旋玻璃三維伊辛模型出發(fā)，闡明三維晶格上自旋排列與統(tǒng)計物理中轉移矩陣的二維特征之間的矛盾導致非平庸拓撲結構。研究確認，自旋玻璃三維伊辛模型存在絕對極小核心模型，為一層晶格自旋玻璃伊辛模型與其最近鄰層自旋的相互作用。它等于兩層晶格自旋玻璃三維伊辛模型減去一個自旋玻璃二維伊辛模型。研究發(fā)現(xiàn)，用蠻力搜索絕對極小核心模型決定其計算復雜度的下限。同時，研究發(fā)現(xiàn)自旋玻璃三維伊辛模型存在NP中間問題，給出體系的計算復雜度的相圖。絕對極小核心模型存在于NP完全問題和NP中間問題的邊界上。進一步，研究根據(jù)自旋玻璃三維伊辛模型和“背包問題”之間的映射，證明“背包問題”同樣存在絕對極小核心模型和NP中間問題，給出“背包問題”的計算復雜度相圖，并證明“背包問題”的計算復雜度的下限是亞指數(shù)、超多項式的。
該研究以物理思想為指導，分析體系的數(shù)學結構，提出一個判據(jù)，確定了NP完全問題的計算復雜度的下限為（1+無限小）的N次方。同時，這一成果為NP完全問題的數(shù)值計算提供了指導性思維。
上述研究建立了“背包問題”與自旋玻璃三維伊辛模型的聯(lián)系，并根據(jù)兩個問題的關系確定了“背包問題”的計算復雜度的下限。同時，該工作得出的結論有望直接推廣應用，來解決計算機、物理、化學、生物、數(shù)學和材料科學領域相關的基礎科學問題。
相關研究成果發(fā)表在《AIMS數(shù)學》（AIMS Mathematics）上。
論文鏈接
自旋玻璃三維伊辛模型最小核模型示意圖
本文鏈接：研究確定“背包問題”計算復雜性下限http://www.sq15.cn/show-12-1209-0.html
聲明：本網(wǎng)站為非營利性網(wǎng)站，本網(wǎng)頁內容由互聯(lián)網(wǎng)博主自發(fā)貢獻，不代表本站觀點，本站不承擔任何法律責任。天上不會到餡餅，請大家謹防詐騙！若有侵權等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。