背包问题算得多快？我国科研给出理论下限

背包问题算得多快？我国科研给出理论下限

【瞧！我们的前沿科技】

光明日报沈阳5月29日电，记者刘勇、王鲁婧，日前获消息称，中国科学院金属研究所，该所张志东研究员，首次确定了“背包问题”的计算复杂度下限，在该领域取得重大理论进展，相关成果近来发表于《AIMS数学》。

计算机科学里，“背包问题”属于经典的NP完全问题，也就是非确定性图灵机多项式复杂度求解的决定问题，它能够应用于不同领域的决策方面，像是寻找用以减少原材料使用的、投资组合的相关选择的、密钥产生过程中的等最优化搜寻路径。设想一个情景：面临薯片、巧克力、矿泉水等十几种零食 ，在书包限重5斤的这个前提条件之下 ，怎样去选出“幸福值”最高的组合？这个贴近生活的问题恰恰就是“背包问题”的简化版本。在物品数量超出特定规模之际，哪怕运用最为先进的计算机去求解，仍需耗费如天文数字般的时间，然而计算复杂度下限则是解决问题所必须的最少时间，这一点是毋庸置喙的。

据介绍，张志东在开展了长达10余年的三维伊辛模型研究工作后，建立起了“背包问题”还有自旋玻璃三维伊辛模型之间的联系，并且依据这两个问题所存在的关系，确定出了“背包问题”的计算复杂度下限。

其中微观磁针（自旋）像一群闹别扭小朋友的自旋玻璃，是一种特殊磁性材料，有的执拗向上，有的坚持向下。张志东把“背包问题”中每个物品的“拿或不拿”对应为磁针的“向上或向下”，寻找最优解相当于在这群互相拉扯的“磁针小朋友”中找到最省力的排列方式（最低能量状态）。放在最后。

对微观磁针排列的复杂纠缠结构展开研究，发现其恰似被猫抓得杂乱无章的毛线团，这竟然是致使计算困难的核心所在。张志东将这种纠缠结构的最小单位给找了出来，那便是“绝对极小核心模型”，它宛如毛线团里最为关键的那个结一样，刚刚好卡在NP完全问题以及NP中间问题的分界线上。依据这些情况，张志东又进一步构建出计算复杂度相图，首次清清楚楚地明确了NP完全问题跟稍简单一些的NP中间问题的分界线，进而确定了复杂度下限，证明最优算法的时间复杂度起码为（1 + 无限小）的N次方，明显远超现有算法。

这项科研成果，突破了以往常规性的认知范畴，证实了NP完全问题存有亚指数级别的算法，还首度精准界定了“背包问题”的计算速率极限。在该领域内的专业人士表示，此项研究得出的结论能够直接予以推广运用，用以解决计算机领域、物理学科、化学学科、生物学科、数学学科以及材料科学领域里一系列彼此相关的基础科学问题。

《光明日报》（2025年05月30日 08版）