IT之家 6 月 1 日消息，中国科学院金属研究所张志东团队首次精确确定计算机科学经典难题“背包问题”的计算复杂度下限，在该领域取得重大理论进展。
IT之家注：“背包问题”是计算机科学中经典的 NP 完全问题 (非确定性图灵机多项式复杂度求解的决定问题)，可应用在不同领域的决策，如寻找减少原材料使用、投资组合的选择、密钥产生等最优化搜寻路径。
举个例子：当面对薯片、巧克力、矿泉水等几十种零食，你应该如何在书包限重 5 斤的前提下选出“幸福值”最高的组合？这个生活化问题正是“背包问题”的简化版。
当物品数量超过一定规模后，即使用最先进的计算机也需耗费天文数字时间求解，而计算复杂度下限就是解决问题所需的最少时间。
据介绍，在 10 余年三维伊辛模型研究工作的基础上，张志东建立起“背包问题”与自旋玻璃三维伊辛模型的联系，根据两个问题的关系确定“背包问题”的计算复杂度下限。
这项研究打破了传统认知，证明 NP 完全问题存在亚指数级算法，并首次精确确定了“背包问题”的计算速度极限，首次明确 NP 完全问题与稍简单的 NP 中间问题的分界线，从而确定复杂度下限，证明最优算法的时间复杂度至少为（1 + 无限小）的 N 次方，显著优于现有算法。
业内专家称，该研究的结论可以直接推广应用，解决计算机、物理、化学、生物、数学以及材料科学领域一系列相关基础科学问题。相关成果已发表于《AIMS 数学》（DOI : 10.3934 /math.2025538）。
0 条