北京中新网5月27日消息，记者孙自法获悉，中国科学院金属研究所的张志东研究员近日在计算机科学领域取得重大突破。他给“背包问题”的计算复杂度上限找到了精确的数值。通常情况下，这个问题意味着发现了计算机运算速度的极限。 这个关于“背包问题”的研究论文发表在美国数学科学研究所出版社的《数学》期刊上。背包问题是计算机科学里的一个经典NP完全问题。它需要在物品数量超过一定限度时，使用非常强大的计算机进行长时间计算。张志东研究员把这一难题转化为微观粒子的两种自旋状态，将价值最大化问题变为寻找系统最低能量状态。通过这些方法，他给复杂度下限下了一个明确的定义。他还在这个过程中描绘了NP完全问题和NP中间问题之间的分界线。 中国科学家破解这个复杂度之谜有着广泛的应用价值。它能够帮助解决物流运输领域中集装箱装载优化方案问题、金融投资领域中收益最大化的投资组合问题以及材料科学领域中寻找原子排列方式最优解等诸多问题。 张志东研究员为了得到这个结论进行了十多年三维伊辛模型的研究工作。他发现把每个物品的选择对应到微观粒子两种自旋状态时，复杂度的本源在于三维晶格中自旋排列的特殊拓扑结构。进一步构建计算复杂度相图，他就揭示了最优算法时间复杂度至少为(1+ε)^N（ε为趋近0的正数），显著优于现有1.3^N的算法。 中国科学院金属研究所表示，张志东研究员在研究中把物品选择对应到微观粒子的两种自旋状态，并将价值最大化转化为寻找系统最低能量状态。这次发现给NP完全问题和NP中间问题之间的分界线做出了描绘。这样就把最优算法时间复杂度确定下来了。 业内专家指出，“背包问题”可以映射到许多其他科学领域里的问题上去。这次中国科学家破解了复杂度之谜之后的结论可以直接应用到计算机、物理、化学、生物、数学以及材料科学等基础科学领域里去解决一系列相关问题。