中新社北京5月27日电，记者孙自法从中国科学院金属研究所获知，该所张志东研究员最近给计算机科学基础理论领域注入了一针强心剂，首次把“背包问题”的计算复杂度下限给精确确定了。说白了，就是搞清楚了到底能有多快。 大家都知道，“背包问题”是个经典的NP完全难题，老早就惹得科学家们心痒痒。这就好比让你背着一个有限容量的大包，面前摆着N件价值重量都不一样的东西，怎么挑才能让总价值最大？这事儿看着不难，其实背后藏着大学问。等东西一多起来，哪怕用上现在最牛的计算机，想要算出答案都得花上一辈子的时间。这次给“背包问题”计算速度定了个顶。 这个研究成果现在已经在美国数学科学研究所出版社(AIMS)《数学》期刊上发表了。张志东研究员解释说，“背包问题”里每个物品的选与不选，正好对应微观粒子的两种自旋状态。他把价值最大化的目标变成了找系统的最低能量状态。通过研究绝对极小核心模型，他发现计算速度慢的根本原因在于三维晶格里的自旋排列有着特殊的拓扑结构。 为了更好地理解复杂度到底有多高，他构建了一张相图。这张图就像一个分界线，清楚地画出了NP完全问题和NP中间问题之间的区别。最后他证明了最优算法的时间复杂度至少得是(1+ε)^N(ε是个快接近0的数)。这个结果可比以前大家常用的1.3^N算法快多了。 业内专家都说，“背包问题”其实可以对应到很多别的科学问题上。中国科学家这次搞清楚了背后的奥秘，这结论以后可以直接拿去用，不光能帮计算机界解决问题，连物理、化学、生物、数学甚至材料科学这些领域的一系列基础科学问题都能受惠。