解决背包问题“复杂性之谜”：发现计算速度极限

假定你有一个容量有限的背包，面前有N个价值不同、重量不同的物品，怎样选择物品组合才能使总价值最大化?

这个看似简单的选择问题，其实是一个隐藏的计算谜题——当物品数量超过一定规模时，即使使用最先进的计算机，也需要花费天文数字时间来解决问题，而“计算复杂度下限”是解决问题所需的最少时间。

在计算机科学基础理论领域，中国科学院金属研究所研究员张志东首次准确确定了经典NP在计算机科学中的完全问题——“背包问题”的计算复杂度下限，该结果于5月22日在AIMS数学中公布。

现实生活中，如何优化物流运输领域的集装箱装载方案，如何在金融投资领域构建收益最大化的投资组合，如何在材料科学领域找到最佳的原子排列方式，都涉及到“背包问题”。

在三维伊辛模型研究的基础上，张志东建立了“背包问题”与自旋玻璃三维伊辛模型的联系，根据两个问题的关系，确定了背包问题计算复杂度的下限。

他将每一件物品的选择(取或不取)与微粒的两种自旋状态相对应，将价值最大化问题转化为寻找系统的最低能量状态。

本次公布的结果包括发现“绝对极小的核心模型”，揭示计算复杂性的来源来自三维晶格中旋转排列的特殊拓扑结构;构建计算图，首次描绘NP完整问题与NP中间问题的分界区域;确定复杂度下限，证明最佳算法的时间复杂度至少为(1)+ε)^N(ε正数接近0)，明显优于现有的1.3^N算法。

“背包问题”可以反映为许多其他科学问题。该研究的结论可以直接推广和应用，解决计算机、物理、化学、生物、数学和材料科学领域的一系列相关基础科学问题。