解决背包问题“复杂性之谜”：发现计算速度极限
假定你有一个容量有限的背包，面前有N个价值不同、重量不同的物品，怎样选择物品组合才能使总价值最大化?
这个看似简单的选择问题，其实是一个隐藏的计算谜题——当物品数量超过一定规模时，即使使用最先进的计算机，也需要花费天文数字时间来解决问题，而“计算复杂度下限”是解决问题所需的最少时间。
在计算机科学基础理论领域，中国科学院金属研究所研究员张志东首次准确确定了经典NP在计算机科学中的完全问题——“背包问题”的计算复杂度下限，该结果于5月22日在AIMS数学中公布。
现实生活中，如何优化物流运输领域的集装箱装载方案，如何在金融投资领域构建收益最大化的投资组合，如何在材料科学领域找到最佳的原子排列方式，都涉及到“背包问题”。
在三维伊辛模型研究的基础上，张志东建立了“背包问题”与自旋玻璃三维伊辛模型的联系，根据两个问题的关系，确定了背包问题计算复杂度的下限。
他将每一件物品的选择(取或不取)与微粒的两种自旋状态相对应，将价值最大化问题转化为寻找系统的最低能量状态。
本次公布的结果包括发现“绝对极小的核心模型”，揭示计算复杂性的来源来自三维晶格中旋转排列的特殊拓扑结构;构建计算图，首次描绘NP完整问题与NP中间问题的分界区域;确定复杂度下限，证明最佳算法的时间复杂度至少为(1)+ε)^N(ε正数接近0)，明显优于现有的1.3^N算法。
“背包问题”可以反映为许多其他科学问题。该研究的结论可以直接推广和应用，解决计算机、物理、化学、生物、数学和材料科学领域的一系列相关基础科学问题。
赞一个
IEEE Xplore,EI Compendex,Scopus
2026年计算机感知与神经网络国际学术会议（CPNN 2026）IEEE出版
官方推荐
EI Compendex,Scopus
2026年光电、材料、医工高新技术国际学术会议暨第三届人工智能、光电子学与光学技术国际研讨会（AIOT 2026）IOP出版
官方推荐
EI Compendex,Scopus,IEEE Xplore
2026年智能系统控制、优化与应用国际学术会议（ISCOA 2026）985主办
IEEE出版