题复杂度之谜解背包问我科学家破

　　【瞧 ！背包问题咱们的科学前沿科技】
。

　　光明日报沈阳5月29日电 记者刘勇
、家破解复王鲁婧。杂度之谜日前从中国科学院金属研讨所得悉
，背包问题该所张志东研讨员初次确认了“背包问题”的科学核算杂乱度下限，在该范畴获得严重理论发展，家破解复相关效果近来发表于《AIMS数学》。杂度之谜

　　“背包问题”是背包问题核算机科学中经典的NP完全问题(非确认性图灵机多项式杂乱度求解的决议问题)
，可应用在不同范畴的科学决议计划，如寻觅削减原材料运用
 、家破解复出资组合的杂度之谜挑选
、密钥发生等最优化搜索途径 。背包问题幻想一个场景：面临薯片 、科学巧克力、家破解复矿泉水等十几种零食，如安在书包限重5斤的前提下选出“美好值”最高的组合？这个生活化问题正是“背包问题”的简化版。当物品数量超越必定规划后，即运用最先进的核算机也需消耗天文数字时刻求解，而核算杂乱度下限便是处理问题所需的最少时刻
。

　　据介绍 ，在10余年三维伊辛模型研讨工作的基础上
，张志东建立起“背包问题”与自旋玻璃三维伊辛模型的联络 ，依据两个问题的联系确认“背包问题”的核算杂乱度下限
。

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

　　研讨发现微观磁针摆放的杂乱羁绊结构就像被猫抓乱的毛线团，是导致核算困难的中心 。张志东找出了这种羁绊结构的最小单位 ，即“肯定极小中心模型” ，它就像毛线团里最要害的那个结，刚好卡在NP完全问题与NP中心问题的分界线上。据此，张志东进一步构建核算杂乱度相图，初次清晰NP完全问题与稍简略的NP中心问题的分界线，然后确认杂乱度下限 ，证明最优算法的时刻杂乱度至少为（1+无限小）的N次方，明显优于现有算法。

　　这项研讨打破了传统认知 ，证明NP完全问题存在亚指数级算法
 ，并初次准确确认了“背包问题”的核算速度极限。业界专家称 ，该研讨的定论能够直接推广应用，处理核算机、物理 、化学、生物、数学以及材料科学范畴一系列相关基础科学问题。

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

贵着原创文章，未经授权禁止转载。详情见转载须知。