中国科学院金属研究所研究员张志东确定了“背包问题”的计算复杂度下限。研究报告发表在《AIMS数学》（AIMS Mathematics）。“背包问题”是计算机科学中经典的NP完全问题（非确定性图灵机多项式复杂度求解的决定问题）。“背包问题”的目标是，在限制所有物体权重之和小于或等于最大权重的前提下，最大化所有物体的价值之和。“背包问题”可用来进行组合数学、密码学、商业等领域的计算，还可以应用在不同领域的决策，如寻找减少原材料使用、投资组合的选择、密钥产生等最优化搜寻路径。“背包问题”与自旋玻璃模型的联系是，“背包问题”的二元决定性变量对应于自旋向上和自旋向下两种状态。“背包问题”的权重对应于自旋之间的相互作用。“背包问题”的哈密顿量可以映射成具有偏置场的自旋玻璃模型的哈密顿。因此，通过求解自旋玻璃模型可以求解“背包问题”。研究得出结论，背包问题计算复杂度的下限为（1+无限小）的N次方——即O((1+ε)^N)。

www.aimspress.com/article/doi/10.3934/math.2025538
www.cas.cn/syky/202505/t20250530_5071218.shtml