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