计算机科学基础理论研究 - 中国科学院金属研究所张志东研究员在计算机科学基础理论领域取得突破性进展，首次精确确定了"背包问题"的计算复杂度下限[1] - "背包问题"是计算机科学中经典的NP完全问题之一，研究长期备受关注[1] - 研究成果论文在美国数学科学研究所出版社《数学》期刊发表[1] "背包问题"的定义与应用 - "背包问题"假设有一个容量有限的背包，面对N件价值不同、重量各异的物品，如何选择物品组合使总价值最大化[3] - 当物品数量超过一定规模后，即使使用最先进计算机也需要耗费天文数字时间求解[3] - 该问题在物流运输、金融投资、材料科学等领域都有广泛应用[3] 研究方法与理论突破 - 张志东研究员建立起"背包问题"与自旋玻璃三维伊辛模型的联系，根据两者关系确定计算复杂度下限[3] - 通过将物品选择对应为微观粒子的两种自旋状态，将价值最大化问题转化为寻找系统最低能量状态[3] - 发现"绝对极小核心模型"，揭示计算复杂度的本源来自三维晶格中自旋排列的特殊拓扑结构[3] 研究成果与科学意义 - 首次描绘出NP完全问题与NP中间问题的分界线，确定复杂度下限[4] - 证明最优算法的时间复杂度至少为(1+ε)^N，显著优于现有1.3^N的算法[4] - 研究结论可直接推广应用，助力解决计算机、物理、化学、生物、数学及材料科学领域一系列基础科学问题[4]