中国科学院金属研究所研究“背包问题”计算复杂性下限

最近，中国科学院金属研究所研究员张志东确定了“背包问题”的计算复杂度下限，并在这一领域取得了理论进展。

“背包问题”是计算机科学中经典的NP问题(解决非确定性图灵机多项复杂性的决定性问题)。“背包问题”的目标是在限制所有物体权重之和小于或等于最大权重的前提下，最大化所有物体的价值之和。“背包问题”可以用来计算数学、密码学、商业等领域的组合，也可以应用于不同领域的决策，比如寻找最优的搜索路径，比如减少原材料的使用，选择投资组合，产生密钥。

“背包问题”与自旋玻璃模型的联系在于，“背包问题”的二元决定性变量对应于自旋向上和自旋向下两种状态。“背包问题”的权重对应着自旋之间的相互作用。“背包问题”的哈密顿量可以反映为带有偏置场的自旋玻璃模型的哈密顿。因此，“背包问题”可以通过解决自旋玻璃模型来解决。在“背包问题”中，所有物体的价值和等值最大化在自旋玻璃模型中的自由能最小化。

这项研究分析了非平庸拓扑结构在NP完全问题中的起源。研究表明，自旋玻璃三维伊辛模型在三维晶格上的自旋排列与统计物理中转移矩阵的二维特征之间的矛盾导致了非平庸的拓扑结构。研究证实，自旋玻璃三维伊辛模型有一个绝对小的核心模型，这是一个晶格自旋玻璃伊辛模型与它最近的邻层自旋的相互作用。这相当于两层晶格自旋玻璃三维伊辛模型减去了一个自旋玻璃二维伊辛模型。研究发现，其计算复杂度的下限是由蛮力搜索绝对极小的核心模型决定的。与此同时，研究发现，自旋玻璃三维伊辛模型存在NP中间问题，并给出了系统计算复杂度的相图。在NP完全问题和NP中间问题的边界上，绝对非常小的核心模型。此外，根据自旋玻璃三维伊辛模型和“背包问题”之间的映射，研究证明“背包问题”也存在绝对极小的核心模型和NP中间问题，并对“背包问题”的计算复杂度进行了计算，并证明“背包问题”计算复杂度的下限是亚指数和超多项式。

本研究以物理思想为指导，分析系统的数学结构，提出判断，确定NP完全问题计算复杂度的下限为(1+无限小)的N次方。与此同时，这一结果为NP完全问题的数值计算提供了指导思维。

上述研究建立了“背包问题”与自旋玻璃三维伊辛模型的关系，“背包问题”计算复杂度的下限是根据两个问题的关系确定的。同时，该工作得出的结论有望直接推广应用，解决与计算机、物理、化学、生物、数学和材料科学相关的基础科学问题。

《AIMS数学》发表了相关研究成果(AIMS Mathematics)上。